Thank you for running through all those steps. I've shipped you an email so I can review your store further.
I can appreciate that this is a frustrating situation, and while I wish I were able to resolve this immediately, I'm afraid this issue isn't something that can be fixed here and now. I can't speak about the contents of your ticket here in a public forum outside of letting you know that Michael has taken the appropriate steps to push for a solution. As soon as he has an update, you will be the first to know via email on the ticket you have with him.
Each case is unique. The thread has been ongoing for some time; however, in most cases, flushing the front end cache does remove the tags that are appearing. I've not come across a case like yours, so I suspect it is a rare occurrence. Nevertheless, our teams are looking into the reason behind why our regular troubleshooting steps aren't working, and what steps we can take to get this resolved for you.
Came here searching on google because got the same issue on my store and I have to say that its pretty disappointing, more than a year and its not close to be fixed.
And its a simple thing like manage product tags.
You have to ask support to delete tags your store don't even use anymore? Come on, its ridiculous!