I have the correct solution and definitely doesn't require a factory reset.
My solution is on a PC, but I expect it will work fine on a Mac, I use a Mac too I just didn't try there, I didn't need to since it worked.
The problem, email addresses that are cached and won't go away no matter what you do, is this your problem?
Here are the steps:
Do a full sync as normal to get a currently, up to date backup, just a regular iTunes Sync.
Leave your phone plugged in, and close itunes.
Download http://www.icopybot.com/itunes-backup-manager.htm
If that link doesn't show up it's icopybot search for it, yes it works!!!
Load it, you don't need to register just hit cancel when registration pops up.
Open iBackupBot for iTunes.
Select the correct backup it will have the date and time you just synced and say ".... iphone"
In the Menu bar above click Plugin, Recent Email Addresses (registration pops up again, hit cancel)
You can just delete the addresses causing issues, I just cleared them all to be safe.
Then the button on the Right hover over it, Close Database Editor, that saves the change.
And then choose Restore, and just say okay.
Don't be alarmed it says restoring Ipod, it will say this no matter what the device it, but it's doing the correct restore. When it's finished close it out and I disconnected my Iphone when it started to reboot, and it takes little while to reboot, you get progress screen and then it comes up fine.
You're email accounts related to those address will be removed, but come on that takes literally two minutes to add back, I added yahoo and gmail back.
And that is it, those cached addresses are fricken gone.