We have an executive user who when accessing contacts via Outlook client, upon editing a contact and then trying to close/save the changes, Outlook would try to verify the name of the contact but would be unable to find a match.
The really odd part is that the name it is trying to check isn't the contact that you've just edited.
For example: If I edited John Doe, when I saved the contact, the pop up says, that Outlook found more than one Ralph Malph.
Further, the person Outlook is referencing Ralph Malph doesn't exist in contacts.
His admin, has editing access to his contacts and I saw this behavior on her pc, outlook client but within his contacts.
I created an outlook profile for the Exec on another laptop saw this same behavior.
And of course, I've witnessed the behavior directly on the production machine the exec uses.
There's no rhyme or reason, and the next day the problem was gone, but it came back a few days later.
Attached is an example of the message. In this case, Outlook was unable find a match for "Jane Done"... but I was in John Smith's contact information.
I have fooled with the address book order, but that doesn't change the behavior.
Outlook 2007 SP3
Exchange 2010
You coud try, if having proper access to the Exchange server, to see if there is any mailbox corruption problem.
For example you could use instructions from here: Create a Mailbox Repair Request - especially the ones from section Use the Shell to detect corruptions for a mailbox to see if there is any problem with it and eventually to repair it.