I think that’s feasible. Searching among tens of thousands of tags is still likely to be an unpleasant problem, but there could be some ways to solve that.
I can’t remember if tags have custom fields, or if you’ll need to add a custom table.
Do you have a budget?