I had an idea and did a bit of research. There's a way you could replace the tags without affecting any user groups by using the CSS replacement method for images.
Basically you could have the piece of code in a theme of its own and apply it globally on top of all the other themes. It would just change the tag of a person where they have a certain specific character class around their image and replace it with the url for the new image.
In order for it to work, anyone wanting to change their tag would need to have their own specific class (which would be empty but it would work as a means of differentiating their tags from everyone else's). It would need to appear somewhere in the same section that the tag images falls in. I've looked at the image code and there doesn't seem to be an obvious way of differentiating them already.
Maybe Veks has a straightforward way he could do this, but it would otherwise mean creating a table and having it drop in a class before and after the tag image where their user id or name matches a specific one. Given that this would take a bit of time to do, I can see why Veks might not want to do that when he's planning the move to Elkarte. However, something like that could be put in place so members could have other badges over the long term. I could give him the image change code in about 5 minutes flat, but I think the complex part would be adding the specific class in for the right person unless there's an easier way.