Short answer: Delete your NK2 file.
Slightly longer answer: In the C:\Documents and Settings\<user
name>\Application Data\Microsoft\Outlook directory there should be a file
with an NK2 extension. Deleting it should clear the auto-suggestion cache.