Even though this question seems to be based a lot on "hearsay", I'll give you my best shot.
Can Tridion Categories and Keywords be used to build a taxonomy-driven website? Absolutely YES.
I know of two things you need to pay attention to:
- Dimensions on your taxonomy
- Cache
Dimensions
A taxonomy can have many types of relationships defined. You can have the basic "tree-like" hierarchy, you have the "related keywords" concepts, and you have potentially additional keyword fields in keyword metadata. When a category is published Tridion will try to create an OWL representation of this. I've heard of one case where about 40,000 keywords were expanded to nearly one million representations in OWL. Publishing this category could take up to 12 hours (!) mostly on the deployer side. Clearly a situation to try avoiding. So, manage your dimensions.
Cache
Tridion will do its best to load the taxonomy only once and keep it in memory as much as possible, as long as cache is enabled. Do NOT even try to do this without cache enabled. Yeah, I hear you saying "of course", but you'd be surprised how many Tridion sites run without cache (it's great for consulting though, you can fix a seemingly complex performance issue within 2 hours).
There's quite a few sites out there using taxonomy, and its performance improved significantly in 2011 SP1 and later.
It has to be clear that Tridion Taxonomies are not meant to replace real taxonomy-management tools that sell by prices that dwarf Tridion license costs. For those, you have specialized Product Information Management tools that can deal with Million+ records and associations and still deliver results in the low millisecond range (tools like SDL's Fredhopper).