Hi

I am not sure why, but the module does not delete the taxonomies registered on search index tables so when you search for a deleted taxonomy, it returns no-named results.

For solving this I've modified sightly the hook taxonomy_search_taxonomy

From this:
case 'delete':
// TODO - delete the indexed search item
db_query("DELETE FROM {search_index} WHERE sid = %d AND type = 'taxonomy'");
db_query("DELETE FROM {search_dataset} WHERE sid = %d AND type = 'taxonomy'");
db_query("DELETE FROM {taxonomy_search} WHERE tid = %d", $tid);
break;

To this:
case 'delete':
// TODO - delete the indexed search item
db_query("DELETE FROM {taxonomy_search} WHERE tid = %d", $tid);
if (function_exists('search_wipe')) {
search_wipe($tid,'taxonomy');
}
break;

Now it deletes the sids of deleted taxonomies