So I finally invested in getting our product feeds up to the point where they are completely error free and also paying $59/month for a feed management software. We're currently submitting to Google/Shopzilla/Nextag.
Nextag and Shopzilla are a work in progress but there seems to be some promise there. With Google however, the results are excellent.
We only get about 10% of the clicks and conversions as we do with the normal PPC bidding, but our conversion cost is about $6 compared to PPC bidding of around $20+. And for people who complain that Google Product Ads used to be free, previously when I did have our feeds completely up to date, we got almost no traffic or conversions from Google Products.