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