iPhone 3G cannot send mail - rejected by the server because it does not allow relaying

I am trying to send an email from my AOL account from my iPhone 3G, however everytime I try and send a mail I get the following error:

Cannot Send Mail

A copy has been placed in your Outbox. The recipient was rejected by the server because it does not allow relaying.

I used to be able to send emails from this handset and haven't had this phone connected to iTunes for a few weeks now.

In general, this is probably because one of, or a combination of the following reasons:

1. Outgoing mail server requires authentication

To avoid abuse by spammers, many outgoing mail servers require authentication for relaying messages across the the internet. You should check if the outgoing mail server you are using for this account requires authentication, and if so properly set it up in your account settings. These typically use the same credentials as the ones for checking your mail with the same provider.

2. Outgoing mail server only accepts connections from the same network

Many ISPs only allow connections from hosts which are connected through their own network. If sending mails through your ISP's outgoing mail server works fine from your home Wifi, but stops working over a cellular data connection, or an external Wifi hotspot, this probably is the case.

In this case you can use another outgoing mail server. If you have a Gmail or an iCloud account you can use those outgoing servers for sending mails.

3. Incorrect settings

Double-check the settings for your outgoing mail server as they are specified by your email provider, especially server name, encryption and the port to connect to. If everything looks ok, try to recreate the account. For AOL and other popular services, there are presets for creating a new account which will fill out all the correct server details.

The specific settings for AOL's outgoing mail server are specified here:

SMTP Outgoing Server Address: smtp.aol.com (Use port 587 for standard or 465 for SSL connections)
SMTP Username: [email protected] (or @love.com, @games.com, etc.)
SMTP Password: password you use to login to Mail

For a secure connection, check the SSL option for IMAP/POP and TLS for
SMTP in your mail program.

I was able to receive emails on my iphone 4, however,I would get the "failure notification" when trying to send an email. Go To: settings/mail/choose email account/SMTP settings/primary mail server. Make sure you have your user name and password keyed in under the Outgoing Mail Server information. This fixed the problem for me. Hope this helps!