"The address "[properly formed address]" in the "To" field was not recognized. Please make sure that all addresses are properly formed.
I received this message after trying to make contact with someone offering a job by replying to their e-mail address in Gmail. The address was proper: no spaces, no unusual punctuation...
If found that someone else had encountered this issue, which later resolved, but no solution, here, http://www.google.com/support/forum/p/gmail/thread?tid=2f751498eaf2a3ea&hl=en
The job requirements did include, "Computer Literacy", however, which among business types is inspeak for "Comfortable Microsoft Product User", and this was a personal assistant position. That bugged me from the moment of encountering this problem. It was not that the address they had provided was originally well formed (there was a space inside of it), but I took care of that before sending.
What I suspected is perhaps an encoding method problem in one of the characters that resulted in an incompatibility: inconceivable these days maybe, but nonetheless suspected. I copied the address into a text editor and then back in to Gmail's "To" field and tried to send: same error.
So I put it back in to the editor, then below re-typed it, took that result, pasted it in to the "To" field, and pushed send...
The mailing was successful.