Noting for posterity that we were able to resolve this. There is an underlying issue where a tag can become “trapped” behind the allow_staff_to_tag_pms site setting if the the tag was only applied to PMs before that setting was disabled.
The workaround until there is a fix is to re-enable the setting and either remove the tag from any PMs, or you can just add it to a normal topic before disabling the setting again.