One of our projects contains a taxonomy with a depth of 10 levels and and with more or less that 6000 terms.
The customer wasn’t satisfied by de design of the standard "TaxonomyWebTaggingControl" because of the reason that it doesn’t show the term-path.
If you have multiple terms with the same name then you have a visual problem .
Looking for a term is more or less good, you just start typing the starting characters and the OOTB term picker will give you a short result list.
In the screenshot below you see that I already selected two terms "Généralités", searching for them was easy but I don’t know or see the path anymore…
I’ve used an own implementation of the AJAX autocompleteextender control which works with my own taxonomy webservice.
The results of the autocomplete search is being put in an SPDataView component.
For displaying HTML in the autocompleteextender I must give the credits to http://theoldsewingfactory.wordpress.com/2008/12/11/arbitrary-html-in-the-autocompleteextender/
The screenshots below give an visual idea about the implementation in a custom advanced search screen: