A reader had this question about lost e-mails on their iPhone. His iPhone was destroyed and along with it some e-mails he wanted to keep. While his music and photos were backed up to iCloud, his e-mail was nowhere to be found. I checked to find out his e-mail provider and he was using AOL. So I had good news for him. His AOL e-mail should be right where he left it on AOL’s e-mail server.
Generally only items related to iTunes or Apple will back up to the iCloud. Your AOL e-mails are located in AOL’s cloud.
If he logs onto AOL.com and into his e-mail account, any messages that haven’t been deleted should still be in his inbox. You really don’t store your e-mail messages on your phone. You just access them from AOL’s server using an App.