The whole post 9-11 environment makes me want to suggest that wives simply retain their maiden name as their legal name. My wife did that when we got married twenty years ago, and it's made things so much simpler for her to not have to reissue ID, change medical records, and so on. For social invites and such we are still Mr. and Mrs. (husband's last name). Her driver's license, passport, and everything official is still according to her birth name. And if someone thinks we are just unmarried living together, so what? (especially nowadays).

The OP's whole sad saga reminds me of two common themes -- 1. When there is a ticketing problem, having a travel agent (expedia) just gives the airline an excuse not to deal with its customer's problem. And -- 2. Airlines and "travel changes" are two things that rarely mix well together.