Exchange Message Refused For Internal User

I have a user who, starting 3 days ago, intermittently gets the following NDR when sending to internal users:

You do not have permission to send to this recipient.  For assistance, contact your system administrator.
            <mail.<redacted>.com #5.7.1 smtp;550 5.7.1 Requested action not taken: message refused>
(The mail server generating the NDR is his mail server)

If the user tries to send from his Android phone or webmail it works.  Also, Once the user restarts outlook he can again send to internal users for a random period of time.

It seems like a problem with the users local PC/Outlook, but I am at a loss for what could be causing it.
One other piece.  The user with the problem is on Exchange 2003 and is sending to users on Exchange 2010.  As previously stated this only started happening 3 days ago and nothing on the server side has changed or the users PC to the best of my knowledge.
Who is Participating?
PradeepConnect With a Mentor Commented:
Try by recreating profile in outlook.
MikeOrsoAuthor Commented:
I have recreated his Outlook profile this evening.  Will monitor tomorrow to see if the problem re-occurs.

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.

All Courses

From novice to tech pro — start learning today.