First Question that must be asked:' Did you recreate the tags?' Make sure you issue 'delete tag all' before you recreate the tags.

How often do you reindex or recreate tags for that table?