Категории иерархические, там одна кухня. Есть теги, которые не имеют иерархии, с ними будет шустрее. То же касается произвольных таксономий. По тегам есть длительный опыт работы с сайтами где их от 3 до 12 тысяч, проблем нет. С иерархическими таксономиями есть опыт по несколько сотен штук с вложенностью до 4-5 уровня, проблем тоже не замечал.
Если запросы начинают выполняться дольше разумного, нужно использовать object cache, если кроме запросов у вас еще своя логика на уровне PHP которая тоже ресурсы требует - используйте fragment cache. И все будет хорошо.
