|Autocompletion of addresses uses a separate list of the last 29 addresses you sent messages to, not the contacts list and it is stored in the registry.|
HKEY_CURRENT_USER\Software\Microsoft\Windows Mail\Recently Used Addresses
If you enter an incorrect address it will stay there until you enter 29 more and it is knocked off the list.
The Geek has a method where you go in to the registry and delete all the addresses listed in the right pane except the Default one and they will reestablish their self when you enter more addresses.
I know this doesn't solve your problem but maybe help you understand the reason.
If you go to Windows Live Mail the autocomplete will work.