I am using Windows 8 with Outlook 2013. I have one Exchange (Office 365) account and one Google Apps account using the Google Apps Sync software.
Occasionally, when replying to an e-mail or writing a new e-mail, I'll get an error reading "Messaging interface returned an unknown error. Cannot resolve recipient." It doesn't matter which account I try to send it from. However, the common thread does seem to be that it only happens with recipients not in my address book. Adding a recipient to my address book does seem to resolve the issue.
Searching online, I found suggestions that this could be caused by a corrupt PST file and used a tool to correct my PST file. This made no difference.
How can I resolve this? Adding recipients to the address book or logging in through the Gmail Web interface are workarounds but not really satisfying solutions.