Clearly the successor solution is to use eight groups of four hexadecimal digits each, separated by colons. Then each individual seat and peanut could be addressed to it's final destination. More seriously the solution suggested of giving the 3 companies other unused prefixes like D* U* and A* to use with their codeshares and non rev flights to start seems the easiest.
Having multiple prefixes per airline doesn't seem trivial, given that this historically wasn't a thing. I could imagine a bazillion code snippets of if flightNumber.startsWith(OUR_AIRLINE_CODE) that might be incredibly painful to fix on short notice.
Especially if they got proper tests.
Certainly way easier than replacing use of a deprecated API (and people do this kind of stuff all the time).