Or, if you mean contacts in the auto-complete list:
Windows Mail auto-completes from a separate list of 29 addresses you type
in, not from your contacts. This list is stored in the registry.
If you wish to remove old or incorrect addresses, there is a utility to
clear recently used email addresses in Windows Mail...