OK.
Another possible search issue: When I constrain a search to "search title only" or "search title and description", the search results come back blank for strings I know exist in our product titles. This happens in RP 3.1 as well.
You can try it here with RP3.1:
http://www.slrgear.com/reviews/search.php
Enter "tested" in the keywords field, select "search title only" and select "All Categories". You get 0 hits. Repeat, but change select to "search title and description". Still 0 hits. Now select "search all fields". You get 31 hits. Could it be our product titles are not the fields being searched?