Penso che sia fattibile. La ricerca tra decine di migliaia di tag è ancora probabile che sia un problema spiacevole, ma ci potrebbero essere alcuni modi per risolverlo.
Non ricordo se i tag hanno campi personalizzati, o se dovrai aggiungere una tabella personalizzata.
Hai un budget?