Have you tried forcing the Recipient Update service to rebuild it's internal database list of users. This might encourage the message to go away? Check the event logs afterwards for any error messages.
Open Exchange System Manager, expand Recipients, Select Recipient Update Service, then right-click on the Recipient Update Service (YOURDOMAIN) in the right-hand pane and choose rebuild and click Yes.
What service pack level is your exchange server? You may need to update it with SP2
Right click your server and choose properties from within Exchange Server Manager
http://www.microsoft.com/Downloads/details.aspx?familyid=535BEF85-3096-45F8-AA43-60F1F58B3C40&displaylang=en