There isn't enough information in your question to provide a "perfect" answer. I tend to think that you might be barking up the wrong tree, but I do so by assuming a few things as follows.
I assume:
- you have so many (single) product pages now, Google hasn't crawled them all (more than 100,000?)
- products will come and go with such frequency that spidering is a never-ending concern, and of critical importance
- without a sitemap, you probably won't get a crawl of all product pages so you rely on the sitemap to expose all pages you need crawled
My suggestions:
- architect a browseable hierarchy for the benefit of the spiders (only); it's clickable by users, of course, but it's purpose is just for the spider to crawl
- the browse hierarchy needs every product to be no more than four pages deep
- construct your URL rewrite to follow the crawl (i.e. first directory = product-catalogue (or similar such phrase), second directory = drill down to first level of product specificity (i.e. "storage"), last directory = a keyword, a hyphen and product ID, last bit of URL string is Product-Name.html)
- design-wise, show the browseable directory links insignificantly to users; you really made this for the spider and from a usability standpoint, it's better if your users click through the existing UI
- steer the spider by designating all other internal links as NoFollow (some may say not all other internal links; whatever the follow/nofollow approach, you need to encourage the spider to travel the easy hierarchical path, and not bounce around the site using all the other natural links)
In summary, what I'm saying is that you should not make a page for every combination of products, afterall, that's an infinite number and an impossible task. Respectfully, I disagree with your SEO guy and @Eric. Instead, I'd be certain to architect a browse-able "catalogue" for the benefit of the spiders, and marry your URL rewrite logic with the drill down clicks AND also your anchor text as the spider drills down. I'd be happy to share with you a URL to serve as an example outside of this forum (email: chris@adragna.com).
If you're still considering the combo pages, the existing URL logic you wrote and the site maps, work with this math: you can have up to 50,000 URLs per map and up to 1000 site maps. That a maximum of 50 million pages... if you want to work backwards from that you can use it to figure out the upper limits of how many product combinations to spin out.
