Override _getSearchableProducts function in class Mage_CatalogSearch_Model_Resource_Fulltext so that it always searches in-stock products.
File to modify: app/code/core/Mage/CatalogSearch/Model/Resource/Fulltext.php
/**
* Retrieve searchable products per store
*
* @param int $storeId
* @param array $staticFields
* @param array|int $productIds
* @param int $lastProductId
* @param int $limit
* @return array
*/
protected function _getSearchableProducts($storeId, array $staticFields, $productIds = null, $lastProductId = 0, $limit = 100)
{
...
->join(
array('stock_status' => $this->getTable('cataloginventory/stock_status')),
$writeAdapter->quoteInto(
'stock_status.product_id=e.entity_id AND stock_status.stock_status = 1 AND stock_status.website_id=?', // add stock_status = 1 condition
$websiteId
),
array('in_stock' => 'stock_status')
);
....
}
Remember to reindex "Catalog Search Index" afterwards.