Unfortunately, according to Google, the only way to do it is by restoring and selecting "set up as a new phone", not from a backup. There is no "empty cache" for Mail on the iPhone.
Personally, if it bothered me, I might try just deleting the email account from the phone, rebooting, and setting it back up to see if that clears out the old addresses. Actually, if that didn't work, I'd consider it a fairly glaring security issue.