If it's a problem for only 3 airlines in the world, give them a new two letter code, if there are any of those codes left. So airline AA will start using also code ZZ for some of their flights. Travelers will be a little puzzled at first but they'll stop noticing soon.
I sorted the airlines by two letter codes [1] and the list is pretty busy but hex 20 for Space is still available.