There is another way around this. You say that you have to fill out a form to get a listing of products. Can you set up a script that takes your 100 or so most popular "searches" that will list the actual products available? What we do at EPage Classifieds (where we have a similar issue with transitory content and a database driven site) is we created an area that can be indexed that replicates popular searches.

Essentially, you will have a map to pages with current results for popular terms. See http://epage.com/classifieds/B.html for an example of one such page we created. You can follow any link to a page that has 10 results that match this. Because the second page is from the database, there are no missing results.

Finally, create a custom 404 page that makes sense and has content for your users. If the product is not there any more, make a simple page that has links to a search, popular categories, info about your site, etc.