[jonnythan]

Dagger. Change your phone so it doesn't sync "all contacts" and instead only syncs the "My Contacts" group.

Gmail will not automatically put any addresses in the "My Contacts" group. Only add the contacts you want to have in your phone in the "My Contacts" group. Then you will have your most important, properly-formatted contacts on your phone and they will be synced with and backed up at Gmail.