Assuming you're using Outlook 2002 or 2003:  The AutoComplete feature works
against addresses you've previously typed in when addressing a message, and
it does indeed have a cache file.  If you want to delete individual entries
from the cache, start typing in a name and when the list of matches comes
up, point to the entry you want to delete (so that it's highlighted) and
press Delete.  To delete the whole cache and start over, look for a file
with an .NK2 extension and rename it or move it.  Outlook will start a new
cache file the next time an e-mail address is typed into the To: box.

Note that if you're using Windows 2000 or XP, you'll need to search in
hidden and system folders to find the .NK2 file (it also helps to have file
extensions visible).