I'm not sure I understand your question correctly.

You want to show categories which match the search query, correct?

I would implement a new block, add it via layout.xml to the catalogsearch_result_index and/or catalogsearch_advanced_result.

The block only needs to get all the categories which match the query, here you need to define whether you want like or fulltext search, or something more complex.

Then you need a template, iterate over all the categories and output them.

OP noted that setting the website IDs seems to resolve the issue:

$products = Mage::getModel('catalog/product')->getCollection();

foreach($products as $product){
    $product->load();
    echo "Disabling product: ".$product->getSku()."\n";
    $product->setStatus(2);

    $product->save();

    $product2 = Mage::getModel('catalog/product')->load($product->getId());
    echo "Enabling product: ".$product->getSku()."\n";
    $product2->setWebsiteIds(array(Mage::app()->getStore(true)->getWebsite()->getId()));
    $product2->setStatus(1);

    $product2->save();
}