That's a good question. It's easy to figure out on Desktop, but not Server. I may need to do the same thing in the near future, so I was looking around too, and so far haven't found any good steps for "deauthorizing".
It may require a call to you customer service rep. ??
EDIT: check out Deauthorizing ArcGIS Server 10 same topic. summary, sounds like you don't deauthorize, but instead use the same ECP. If I remember correctly, it may take the customer rep to allow additional authorization with the same ecp, even if your myesri says 0/1. That is just something I have floating around my memory.