I know this is late, but I thought I'd add something. Right now, the USA is pretty ugly when it comes to marriage and people who are intersexed or who have a gender different than what was misidentified at birth.
I think these marriages are safe in the entire USA:
1) Any marriage where one partner has male body parts, the other has female body parts, one partner is XX, one partner is XY, and where both partners have legal identification that is consistent with gender markers, such that it always indicates the partners are opposite sex. This includes the case where both partners have transitioned. Chromosomes, body parts, and identification don't need to match, but they need to always allow people to see both partners as "opposite" no matter what random standard is chosen. The only possible complication is states that label the sections of a marriage license "husband" and "wife" - it's possible that the state could say you lied on the application if the "wrong" person in the state's eyes filled out the wrong section.
2) A marriage that existed before someone transitioned, and met #1 before they transitioned.
3) A marriage that would have met #1, except for the removal of body parts.
I think the above marriages would be valid everywhere in the US. For any other marriage, we will not be recognized in all US jurisdictions. The problem is the combination of state and federal rules in the US. The only people that someone who has had SRS can be married to and be "safe" everywhere is someone else who had SRS (and is the opposite sex and gender).
Right now, part of the problem is that almost nowhere has actual legal statutes defining male and female. It's up to whatever the courts randomly (and they seem to be very random here) decide. In many cases, the courts haven't decided on this yet at all, so nobody knows how they would decide.
In some states, I am married to my wife. We are in a heterosexual marriage, at least in my eyes and my wife's eyes (and the person's who issued us the marriage license). But in some states, I'm not married. Even in the ones where I am married to her, that marriage could be deemed invalid at any time - either the marriage could be challenged there or it could be challenged in the state where we were marriage. Federally, I don't think there's enough knowledge to know if it would withstand a federal challenge. It's a huge mess.
It's all about "keeping gay people in line" - too many people want government in charge of our bedrooms, and want to tell us who it's okay to have sex with. Somehow, this gets translated to "if we prohibit marriage of gays, we won't have gay sex in America and thus America won't be destroyed by God." Ironically, this ends up prohibiting heterosexual marriages (like mine) in some states, not that this makes things more or less wrong.
Two things need to happen to fix this. First, DOMA must be repealed or invalidated. DOMA allows states to not recognize marriages performed in other states. "Cismarriage" never has to worry about this - but we do. DOMA doesn't allow states to question the scenerio in #1 - if another state says a cismale and cisfemale is married, even if they couldn't have been married in a different state. For instance, first cousins who are cismale and cisfemale who marry each other in Alabama (legal there) and then move to Arkansas (they couldn't have married there) are still married in Arkansas - and Arkansas is prohibited from invalidating the marriage. But if both partners aren't cisgendered and of opposite gender and sex, then this states can now refuse to recognize a marriage granted by a different state. It's a double standard and wrong. If my wife and I were traveling cross-country, and she died, her body very possibly would not be released to me, her husband, but rather to her parents. This is a huge wrong (and affects other areas such as medical care - particularly things like expressing end of life wishes, taxes, etc).
So, getting rid of DOMA is a big important step.
Second, we need to ungender marriage. Civil unions are not good enough - in most places that have them, you can't have both a civil union and a marriage, so a marriage where a state might decide someone is a different gender than they are might choose to say that they entered into the marriage or civil union under false pretenses. They might say, for instance, that my wife was really male, so I should have "unioned" her instead of marrying her. But, since I didn't, I'm *neither* unioned or married. Marriage licenses should not even ask for sex of the partners even in states that allow same sex marriage - unless there is law defining how to answer that question - lest they say the married couple lied on their application and thus declare it invalid.
I'd also add one more criteria that has been used to invalidate a marriage. If a spouse didn't know that their spouse was previously seen as a different sex than they currently are, and married thinking that they were marrying a cisgendered person, at least one court has decided that this was essentially marriage under false pretenses and thus invalid. This is an additional issue, in addition to getting rid of gender in marriage law, and probably should have some law to actually protect people (not being "told" should be explicitly defined as something that cannot invalidate a marriage). But this probably isn't going to happen anytime soon, so people who want their marriage to be the most protected should make sure that both spouses can prove that the history is known (they might be challenged not just by each other, but by a third party such as a life insurance company).
It's an ugly situation in the US right now.
