I was pulling my hair out wondering why this simply feature was not working. Turns out the MySQL user needs to have rights to create temp tables. If not, the cart will simply return no results and no error messages ---- which is why I was going nuts trying to troubleshoot this problem.
So - if you have search troubles make sure the rights are setup on MySQL! 