An obscure tip but one that I found worked this week.
A colleague at work was attempting to send a meeting request but repeatedly received errors from our Microsoft Exchange server for one of the recipients. Everything seemed fine and the contacts were correctly populated from the contacts cache. Sending the request met with no resistance from Outlook which made things rather confusing.
Well, it seems the contacts cache in Outlook ended up the culprit and the way the problem was resolved was deleting the contacts as they appeared in the autofill list as you typed out a name. You do this by clicking the X at the end of the row containing the erroneous contact and entering it from scratch.
Once the updated meeting request was sent there were no more errors – hurrah!