After trying to use the inbuilt Google Base feed, I was getting so many errors and issues with HTML etc that I started going through and modifying it with my own classes, with the intent to make the output bulletproof. I was getting there, and then I came across the Open Base Product Feed v1.5.0 by ajbarry99. At the point I was at, I was trying to clean the HTML up, so I gave it a whirl instead of reinventing the wheel.
Brilliant! The only problem I had was the admin had entered a lot of information that was causing issues, like uploading images with spaces in the title, ampersands in the product title, and leading and trailing whitespace all over the place.
I made a few small changes to the Open Base module based on the code I had written for the Google Base module, and it handles these mistakes quite elegantly. Google Merchant accepted the feed right away last night, and my mates store has been listed today!
I renamed it BulletProof OB for my own usage, but ajbarry99 was happy for me to release it as a standalone module. If you are having trouble getting valid feeds, give this a try. It may be that you have a few invalid characters that this should clean up.