I wondered if you could send mail that way or if it also didn’t work.
Windows Mail auto-completion doesn't use the Contacts list (address book). Instead, it uses a separate list of the last 29 addresses you sent messages to. That list is stored in the registry and is not easy to understand or edit. Names can be partially recognized by right-clicking the identifier (a-z, etc.) then clicking Modify. They are stored in the registry key HKEY_CURRENT_USER\Software\Microsoft\Windows Mail\Recently Used Addresses.