I'm no android expert, but doesn't that sound like a virus/rootkit/hijack? I cleanup desktop systems for a living, and that is the general modus operandi for malware: Hijack the system without the users knowledge and use it as part of a botnet network to send out spam.
When you stated that it started when the phone was new, I thought it would be unlikely to be malware that quickly, but then when you stated that you backed up everything from your old phone and moved it to the new one, I thought, you just brought the problem to your new phone.
Update: Wait, how do you know it is sending out email in the background? Just from the bounce backs? If that is the only evidence, then I would say that it is not your phone sending out emails. It is someone else's computer that has been compromised, and is sending out spam using your address as the From address. Thus you receive the bounce backs from bad addresses. At some point the malware picked up your address from someone else's contact list. If the bounce backs are the only evidence you are going by.