This is by design - tags are assigned to machines inside the ePO database, and when the machine is deleted from ePO its entry is removed from the DB, along with anything assigned to it. (The same thing would happen with task and policy assignments.)
Thanks for your quick answer. I was fearing that this would be the answer. We are trying to using Tags to apply different encryption policies. It know means that I have to be more careful when removing systems from ePO.