Windows Mail apparently doesn't actually use your address book but keeps a separate list of the last 29 addresses used and that is where the auto-complete is drawn from:
How do your setup/turn-on auto complete of email address in Windows Mail - Microsoft Answers
Windows
Live Mail replaced Windows Mail several years ago and does a better job of auto-completeing from what I've read (I don't use it).