I cannot find any reference to a "purge recent addresses" in iOS so you might need to just erase all Mail accounts and see if that clears the cache of recent addresses. In fact, I can't even find confirmation that this is something that is even programmed.
Have you tried deleting all contacts from the phone to be sure it's not a problem with the contact database and not simply a mail issue?
Assuming you have a good backup of your contacts (or they are stored safely in the cloud while you are troubleshooting this) - these are your two options for clearing things further with respect to Mail and the data it contains:
- wiping the device and setting it up new
- deleting all Mail accounts and then setting them up again (password, servers, etc...)
The first is a pain, but should work splendidly. The second is not guaranteed to work, but much easier to do and less setup to get all of your data and apps restored and configured again.
I would recommend a good backup before deleting anything and knowing all your passwords before deleting a Mail account (screen captures of each mail settings page is a nice way to document the settings before deleting things). Also - it would be good to log into webmail to be sure that all the messages are still on the server. This shouldn't be an issue with IMAP/Exchange - but POP mail is notorious for deleting messages so you may not want to try this if you're not sure all your email is on the mail server.
Surely a total erase and setting up the phone new would clear this list, but I would start with deleting mail first and then perhaps deleting mail and all contacts to see if the cache of previous recipients gets cleaned out.
Hopefully someone else has a better solution since this isn't something I have tested as I've never had a situation where