The Mini Search (and the default search - http://example.com/catalogsearch/result/?q=searchTerm) is not returning the correct result.
Surprisingly the advanced search is working fine.
After trying out all sort of methods, finding and editing the .phtml, .xml files. I found out that its one of the core files that causes this issue.
Open up app/code/core/Mage/CatalogSearch/Block/Result.php
Uncomment line 149 and 150
Then change line 172
$this->_productCollection = $this->getListBlock()->getLoadedProductCollection();to
$this->_productCollection = Mage::getSingleton('catalogsearch/layer')->getProductCollection();
That solves the search problem.