O básico é que você precisa armazenar tags como está mostrando no primeiro caso. É bom para verificar se a tag existe (já que no segundo caso para tags existentes, seu banco de dados retornaria tantas linhas quanto as aparências da tag) e bom para recuperar itens por tag (selecionar id de item por um id de tag é melhor do que selecionar item ids por um conjunto de tag_id que tem o mesmo significado representacional).

Se você queimou seus dedos por causa da indexação - você deve sempre verificar como a consulta está sendo executada (para mysql é EXPLAIN/DESCRIBE SELECT ).