error message: The recipient xxxxxxx was rejected by the server because it does not allow relaying.
I had this same problem with using my email account on the iPhone 4. I could receive email but it would give me " the server did not allow relaying" message. What I had forgotten was that my server is actually provided by netscape but was merged with aol years back, I don't know exactly how that happened but this is what I did to work around it:
First, I deleted the aol email account from my phone.
Then, I logged into my email account through my computer. I went to the settings tab> IMAP and POP
There I found the IMAP set up information. (Keep this handy)
On my iPhone: Settings> Mail,Contacts,Calendars> Add Account> Other> Add Mail Account
The user name, address, and password I entered was the same that I use to log in through my computer.
To complete the set up I used the IMAP set up information for incoming and outgoing mail servers. The set up took about 5 minutes. It worked with and without WiFi. I am using an iPhone 4 with the updated iOS5.
I hope this helps.