A simpler solution
Don't specify gender on identity documents. It's a dodgy concept in any case, thanks to chromosomal abnormalities, etc, etc, and the form of a person's external genitalia is of very little practical use in checking people's identities as people don't (yet) routinely show their genitalia at passport controls and when stopped by the police. Also, the information content is just one bit.
(On the other hand, a person's apparent sex is something that even the dopiest witness can occasionally remember.)


