By "contacts not recognized" do you mean it doesn't auto-complete
the recipient after typing a few letters? If so, that is a known issue with
Windows Mail. It does not use the Contacts list for auto-completion.
It uses a separate list of the last 29 or so recipients you've sent to.
That feature works correctly on the newer Windows Live Mail.
I recommend you upgrade: http://get.live.com/wlmail/overview