How to remove autocomplete items from the TO: field in Mail?
i have the same problem and unfortunately i believe the only current solution is doing a restore of the phone.  once the phone reconnects to itunes, select set up as new phone and resync your apps and other content over.  you will also have to reconfigure all your settings including mail.