I'd say that the answer is quite simple,
if you disable SEO then search module will work under all categories, but if you enable SEO search module will search the keyword in that particular category.
What I did to quick fix the problem was to add in <form> a new <input>
<input type="hidden" value="0" name="virtuemart_category_id">
and the other thing about "+" and "-" in product names..
you go to administrator/com_virtuemart/models/product.php
and around line 129 find
$this->keyword = vmRequest::uword ('keyword', "0", ' ');
and replace it with
$this->keyword = vmRequest::uword ('keyword', "0", ' ,-,+');
last parameter of uword is allowed characters