Há algum tempo (2013? 2012?) desenvolvi um sistema muito semelhante ao da pergunta. Eu tinha alguns milhões de objetos e uma dúzia de "tags", e cada objeto poderia ter 0 ou mais tags associadas. Eu tinha que filtrar esses objetos baseados em buscas por conjuntos de tags. Semelhante, não?
Como o número de tags por objeto, no meu caso, era teoricamente ilimitado (visto que novas tags poderiam ser adicionadas ao sistema depois de lançado), a solução proposta na pergunta não me servia, i.e., eu não poderia utilizar uma tabela com colunas "tag1", "tag2", etc. Além disso, esse esquema não permite utilização de índices (veja meu primeiro comentário na resposta do @mgibsonbr).
Como eu necessitava de bastante performance (i.e., queries respondidas em "segundos"), na época fiz uma comparação entre diversas soluções, incluindo as duas propostas pelo @mgibsonbr em sua resposta.
A seguir, meus resultados -- se minha memória não falha!
Trade offs...
A solução "1." do @mgibsonbr tem a desvantagem de possivelmente ocupar muito espaço em disco (já que você terá os "caracteres" das tags repetidos inúmeras vezes na tabela toda). Isso é uma desvantagem pois obriga o seu banco de dados a ter que ler muitas "pages" do seu disco rígido, então tem que girar muito o disco e mexer muito a cabeça de leitura, o que pode ter grande latência. A vantagem é que você faz apenas 1 select para obter o seu resultado.
Já a solução "2." do @mgibsonbr utiliza menos espaço em disco (pois na tabela gigante só serão salvos os ids das tags -- e se você utilizar o tipo numérico de tamanho adequado à quantidade máxima de tags, pode reduzir a 4, 2 ou até mesmo 1 byte por linha). Assim, você consegue ler mais linhas por "page" lido do disco reduzindo latência. Em contrapartida, o seu select provavelmente teria um join:
select from tags_objects, tags
where tags.id = tags_objects.tagId
and (tags.name = 'tag-buscado-1'
or tags.name = 'tag-buscado-2') -- etc...
Esse join é o culpado por problemas de performance nessa solução.
Solução mais eficiente (no meu caso de uso específico)
No final das contas, a solução mais eficiente que consegui foi utilizar a solução "2." com 2 selects distintos. O primeiro select busca os ids das tags, e o segundo select utiliza os ids das tags na tabela gigante. É como se eu fizesse o join "manualmente".
Isso era vantajoso para mim pois, no meu caso, era possível eu manter em cache, na minha aplicação, os ids dos tags. Esse cache era atualizado por um thread em background (fazendo um "full scan" na tabela minúscula que contém tags e seus ids a cada "X" segundos). No final das contas, em termos práticos, o cálculo "síncrono" era apenas um select na tabela gigante com a coluna "tagId" sendo algum tipo numérico, portanto menor do que ter que fazer joins.
Obviamente, por questões de performance, é necessário colocar um índice na coluna "tagId" da tabela gigante.
Antes de implementar toda essa solução, minhas queries duravam ~1min ou ~2min com, se não me engano, uns 5 tags. Após tudo isso, consegui reduzir o tempo das queries para algo em torno de ~10s!
Considerações
É bastante complicado analisar de antemão qual será a solução com melhor performance nesse caso, pois realmente depende das características do seu projeto. Espero que esta resposta possa dar alguma orientação para a sua busca pela solução mais eficiente para o seu caso específico.