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.
That would have the additional benefit of being able to tell at first glance if your flight is actually flown by the airline you are booking or by someone else. But I'm not sure airlines actually want this to be that obvious...