According to the Wiki, it's supposed to be removed if you lose your muzzle. However, in testing, that doesn't seem to work.
Looking at the code, the event that gives Androgyny doesn't set a value used by the removal event. I don't know if it's intentional. Using the Save Editor to set the value, the perk is removed properly. I'm filing a bug report.
In the meantime, if you want it removed but don't have the Save Editor, you can upload your save
here, and someone will be along to help.
