I must say, this is an extremely interesting question / problem. You are momentarily put in a tough spot. On one side you want to include all users, while at the other side you need to keep the whole process of buying a ticket smooth so other users will not experience any hiccups.
As one of the early adopters you (and maybe people that read this) are facing a few obstacles.
Laws are part of the problem
One of the first obstacles and probably an important one is the law in your country. In most country's the law is lagging behind customs. The third party suppliers you speak of might be required by law to define a passenger as male/female according to their passport. So even if they want to implement the changes, they can not because of the law.
What can you do?
Personally I did not have this problem yet. The place I work do not have any forms where it is necessary to fill out your gender. I found a long article about gender in forms, it is a long read but worth it.
Now in the article there is an example that looks promising. Take a look:
The first part is them being honest, I believe this is one of the best things to do. You can explain your situation in a hover like they do above. Now how do they solve the problem. You can see it in this GIF(mirror).
What to watch out for
I think that being honest is extremely important. However, there might be consequences if you add this option. One of them is that the user can blame your company when there is some bigotry down the line.
The user confides their identity in you and expects you to guard that identity for them during the whole sale process. However, when down the road (at their holiday destination) they experience bigotry (or some other problems) they feel left out because they thought you had their back.
If you wish to read more, Meera Balarajan, Michelle Gray and Martin Mitchell did extensive research on how to ask the question of gender when monitoring diversity.
I have a friend that is fairly active in the LGBTQ+ community, when I see him I will ask his opinion and edit my answer.