This issue is very common since last couple versions. I found this useful article how to resolve it here in version 1.5. and I recommend to read it if you want to understand how quick search works.

Here is my update for version 1.6. Basically same idea with small changes:

1. Copy: app/code/core/Mage/CatalogSearch/Block/Result.php to: app/code/local/Mage/CatalogSearch/Block/Result.php and uncomment lines 149 and 150:
   $this->getListBlock()
   ->setCollection($this->_getProductCollection());
   Then go to line 172 and change from:
   $this->_productCollection = $this->getListBlock()->getLoadedProductCollection();
   to:
   $this->_productCollection = Mage::getSingleton(‘catalogsearch/layer’)->getProductCollection();
2. Copy: app/code/core/Mage/CatalogSearch/Model/Resource/Fulltext.php to: app/code/local/Mage/CatalogSearch/Model/Resource/Fulltext.php and go to line 356 and change:
   $likeCond = ‘(‘ . join(‘ OR ‘, $like) . ‘)';
   to:
   $likeCond = ‘(‘ . join(‘ AND ‘, $like) . ‘)';
3. In Admin Panel -> System -> Configuration -> Catalog -> Catalog Search set Search Type property to “Like”. Then reindex data, refresh cache…