tedster - 10:50 pm on Aug 22, 2011 (gmt 0)
Hello markward, and welcome to the forums. I moved your thread here to the Google SEO forum as a better place to get input.
Normally, depth of indexing on Google is related to PageRank - and in particular, solid backlinks to internal pages can be a good help. By "solid" I mean freely given "editorial" links rather than links you can just decide to place on your own. This can be challenging for a product "database" type of site, unless you have some remarkable content somewhere - possibly for strong categories within the site. I'd say the key for this site is summed up in two words "content marketing".
If the current product pages are just generic feeds, with the same essential content available on other websites, then the job may be almost impossible. However, if you can enhance that content and add value, things do get better.
And finally, I agree that a sitemap is a good idea - specifically an XML sitemap (at this scale, a set of sitemaps with an index sitemap.) At the very least, you'll get more accurate indexing information from WebmasterTools in that case than you would see using the site: operator.