Do you use Google Webmaster tools ?
You'd get more info about this.
If you create a sitemap.xml, submit to google (via the tools mentioned above), and keep it up to date when you add new pages, you should see improvements in indexing time.
I dont agree with that. Having an XML sitemap wont necessarily increase your indexing time. Raising your profile and authority in Google will. Bing has a different strategy and ranking algorithm and a completely different indexing system to Google. Its very possible that Microsoft have a strategy of having all the most up to date information.
At any rate, being indexed and being returned in the top 3 positions that people actually search for are completely different things, and solution to both is in gaining more authority and relevance.
If you hit the omitted link is there a 'theme' to the pages omitted?
what about duplicates?
is the content in each of the 20k totally unique - possibly not as its ecomm. I'd look at stripping back and looking at canonical tags.
The key though is to have new content to index
You'll find that the more often you update your pages, the more frequently the Google bots will drop by
You need to post unique contents frequently on your website and check your robot.txt setting. Maybe your robot.txt setting disallow robot crawling. Submitting sitemap will help and interlink within articles will help also. Hope it helps.