I was having exactly the same problem until I installed the advanced search mod found in this thread:
http://forum.x-cart.com/viewtopic.php?t=5971
I know it's a long thread but I did this a while ago so my apologies for not pinpointing the exact post.
Hope this helps.
works for 4.0.18.