We noticed a couple of days ago, while investigating submodule tags for Changesets don't detect tag changes in submodules, that the Git repositories were not detecting tag updates and removals correctly. The ‘git fetch’ output had changed since we implemented the code to parse the results. We have now fixed this in development and hope to release a new version soon. With this change in place, the tags get updated correctly in the queue dialog and the correct commit gets built for updated tags.
This could be the cause of your issue, although you said that the cache was refreshed after removing the tag. What options have you selected for Tag Changes in the repository settings? If “Detect and list as new changeset” was selected, do you see a changeset listed in the Changes tab of the configuration related to the tag change?