Two things. First, "personal" tags do not automatically apply to any folder. Think of them as optional tags that you publish, so that users have a choice to apply some different retention settings to a folder. In other words, to have a "working" personal tag, the user must assign it to items/folders.
Second, the Deleted items folder is a bit special. Microsoft decided a while back to treat it differently, as apparently it deleting items automatically caused too many support calls. It should only apply to tags with "delete" action, but I though I'd mention it here just in case.