Maven Release-plugin "tag already exists" for nonexistant tag

Try options "Clean before Build" and "Clean After Build" within Source Code Management -> Additional Behaviors.

mvn release:clean before release:prepare is what worked for me

Shortly after my last discovery which screamed "CACHE PROBLEM!" I found the solution. I deleted all repository-cache-data following the instructions on this site: https://confluence.atlassian.com/display/BAMKB/Git+cache+removal+in+Bamboo

I experienced this error again and again in a Jenkins release build after a release had failed previously. I restored the repository state before the release and verified that the tag did not exist anymore using git tag. To be absolutely sure, I also deleted the tag locally and remotely using:

git tag --delete mytag
git push --delete origin mytag

Both commands reported that the tag did not exist. Regardless, the release build kept failing with

[ERROR] The git-tag command failed.
[ERROR] Command output:
[ERROR] fatal: tag 'mytag' already exists`.

I finally solved this by enabling the option

Build Environment -> Delete workspace before build starts

Hence the problem is that after a failed release build the Jenkins workspace is left with a dirty repository state in which the tag still exists.