I am currently having this same problem on one of my sites running Joomla 1.5.22 | Virtuemart 1.1.6 | PHP 5.3.13
The search always returns 0 results. This happens with the Virtuemart Module (with the Show Product Search? set to yes), and with the standalone Virtuemart Product Search Module. Both show no results.
If anyone has encountered this problem before, please share what you did to resolve.