With sync with the long tradition of Microsoft, Outlook has a very annoying bug which is not fixed as of Outlook 2007 (Technical Refresh). The bug produces the error mentioned in the title of this post whenever you try sending a email with the address which was retrieved from exchange address book.
To re-produce the error:
Create an exchange based email account
Try sending to few people on the exchange address list
Eventually you will be overwhelmed by the disadvantages of Exchange over its advantages, now you remove off the exchange account and recreate the same account using the POP and SMTP option
Now try sending to any email that you had sent before using the Exchange (which will be automatically retrieved from the Address Cache).
Tada! you will get the above mentioned error
From my observation what seems to be happening is that when you sent the message initially using the ‘Exchange’ account, the message’s target emails are formatted by Outlook with some kind of format that the Exchange server is comfortable and happy. But the problem comes up when you change the email type from Exchange to POP and when you try sending email to the cached email address (Exchange type), when that happens the outlook gets an error from the SMTP server saying that the given email format is not proper and so the ‘Send’ fails.
To solve this issue we will have to remove off the existing outlook address cache by renaming / removing the file present at C:\Documents and Settings\%username%\Application Data\Microsoft\Outlook the name of the file will be <Your outlook profile>.nk2. Once this file is renamed / removed you will have restart the outlook in order for it to take effect. And after this sending emails shouldn’t fail for the given reason.