I get the impression that what you consider a dynamic website is not the same thing what we technical people consider a dynamic website.

Your site works with a lot of products that are only temporary available and then the product doesn't exist anymore, and won't exist again, or at least not in the way it was presented before.

Your products can be found only through a search form, which indeed means that search engine spiders can't find your products. Spiders don't fill out forms.

One strategy I would consider is to create a directory structure where a visitor can click through to the desired (sub) category. In all these category pages you can present the products with links to the product pages them selves. Do try to use static urls for the category pages. Do also make sure that you don't create very deep levels. A product page shouldn't be more than 4 or 5 clicks away from the homepage.

Also do create "most popular" areas and other ways to highlight products or categories to create the necessary cross linking in the whole site.

__________________
FREE SEO ! Really? YES! All you have to do is implement it!
Follow me on Twitter PeterIMC