User doesn’t exist. but he does

i get the **The e-mail account does not exist at the organization this message was sent to. Check the e-mail address, or contact the recipient directly to find out the correct address.**

OK here is the background on this migrated user from exch 2k to exch 2k3 and worked fine for several weeks. then all of a sudden his outlook wouldnt connect. he could connect to OWA and still got his blackberry. if i killed his exchange link between AD and mailbox and re-associated with a brand new test account and logged in as that user and was able to open outlook just fine. so i created a new AD account and recreate his mailbox. it worked for a a bit and now unless you type in his exact email address you get that message. any ideas on this at all?