MAPI_E_Not_ME sending to 1 recipient from Outlook 2010 via Exchange 2010

Interesting, out of the blue, one of my users gets an error when trying to send email to another person within the same domain.  The mail is not leaving the campus to the outside world.  He can send to anyone else internally with no issues.  He can even send email to this one person via webmail with no problems at all.  Turning on logging I am seeing the following on the log for the one message:

2011.10.03 16:21:52 MAPI XP Call: SubmitMessage, hr = 0x80040502
2011.10.03 16:21:52 MAPI XP Call: SubmitMessage returned MAPI_E_NOT_ME.

The bounce message he is getting show the following.  I changed the email addresses to a bobo one for privacy:
Delivery has failed to these recipients or groups:
A problem occurred during the delivery of this message. Please try to resend the message later.

Diagnostic information for administrators:

Generating server:

Keep in mind this is ONLY when sending through Outlook 2010.  Webmail has no problems.
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Have you tried setting up a new outlook profile for this user?
Marc DekeyserSr Premier Field EngineerCommented:
Hi, can you check that the user is in cached mode? If you place him in online mode he will probably not have the problem seeing webmail works. Try removing the nf2 file; this file is what automatically fills in the "to" field in outlook and that might have gotten corrupted

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
taphopeAuthor Commented:
Apologies for the REALLY late delay.  This just happened to coincide with a move that central admin started and it has taken most of my time.  Do you know where the nf2 file is located?  I have searched a little bit on google but haven't found anything significant.  
Simplify Active Directory Administration

Administration of Active Directory does not have to be hard.  Too often what should be a simple task is made more difficult than it needs to be.The solution?  Hyena from SystemTools Software.  With ease-of-use as well as powerful importing and bulk updating capabilities.

taphopeAuthor Commented:
I basically removed the account and set it back up but got the same results.
taphopeAuthor Commented:
Strangely enough, removing outlook completely and reinstalling it took care of the issue.  I would assume that it removed the nf2 file that was mentioned earlier.  
taphopeAuthor Commented:
Although I did not find that nf2 file mentioned, I assume that uninstalling and reinstalling Outlook essentially does the same thing only the long way around.  Either way it worked.
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today

From novice to tech pro — start learning today.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.