It seems like a solution to this would be to move away from non-unique tags, and simply make them part of the policy -- or directly tied to it.  That also solves the "garbage collection" problem, in that we now have a *:1 relationship of tag => policy, and can delete any tied tags when we delete the policy.  The obvious change there is to stop referencing tags by "identity" here and, instead, simply include the data.

Failing that, I would suggest that we *still* just put the literal data inline -- and implement "find or create" behaviour for the policy.  If the tag exists, map to it.  If not, create it and map to it.  Viola, an atomic command -- no need to pre-create tags -- that works regardless of the tag state.