The auto-complete in Windows Mail just doesn't work correctly.
It keeps a separate list of the last 29 addresses you've sent to, including
bad ones.
This list is kept in the registry (in binary).
HKEY_CURRENT_USER\Software\Microsoft\Windows Mail\Recently Used Addresses
This is one of the features that works properly in the newer Windows Live
Mail.