It is because the search was designed to search products in the category that you are browsing at that time.
For instance, if you are in the T-shirt category and type RED in the search box. It searches only the RED keyword in TShirt category (and its sub-categories). It won't perform the search in the entire store. Got it? But looks like you don't want this feature.
Try this trick to make the "search module" to perform the search in the entire store always, no matter which category you are in.
Open this PHP file:
/template/YOUR_TEMPLATE/html/mod_virtuemart_search/default.php
and find this line:
<form action="<?php echo JRoute::_('index.php?option=com_virtuemart&view=category&search=true&limitstart=0&virtuemart_category_id='.$category_id ); ?>" method="get">
and replace it with this:
<form action="<?php echo JRoute::_('index.php?option=com_virtuemart&view=category&search=true&limitstart=0'); ?>" method="get">
Regards.
Forum Support.