Предложил бы копать в сторону Views.

Да, простое и элегантное решение

Хм, да есть же он для 6.х. Ну, конечно бета, и иногда надо слегка пропатчивать, но работает.
Хотя, если найдется рабочая альтернатива под 6.х, будет очень даже хорошо, а то, у HS легкие проблемы с поддержкой мультиязычности и таксономии.

Я бы рекомендовал, для пробы отключить Pathauto, очистить кэш, и посмотреть работает ли Taxonomy Redirect вообще.

Если проблемы в Pathauto, то смотреть что он прописывает для таксономии.

Ещё есть модуль Ubercart Marketplace, который как бы расчитан на создание конфигураций с множеством продавцов.

А pathauto настроен как ? Может конфликт модулей ?
Должен заменять ссылку у термина входящего в заданный словарь.
Правда, если ссылка вытягивается не через ф-цию taxonomy_term_path а через URL taxonomy/term, то заменять не будет.

Может стоит добавить в хук меню :

'type' => MENU_CALLBACK

У меня без проблем работает. Может кэш ?

Подобное решается просто при помощи Taxonomy Redirect.

Термины разносите по словарям. В таксономи редиректе указываете алиасы. В Views под каждый алиас корректируйте вывод как хотите, или делайте отдельные вьюсы под каждый алиас.