For a project at work, we needed to be able to manage, and therefore search, large-scale taxonomies (10,000+ terms). Users needed to be able to search for term names, descriptions and synonyms, so I figured a module using the Drupal search API seemed to be the best bet for a solution. I dove in deep and came back up with Taxonomy Search 2.x.
I've just released version 2.0 of the module, and you can check it out at the Taxonomy Search project page. I'd love some feedback, as this is my first module that utilizes the search API, and there may be some rough edges. Please take a look at let me know what you think!