Aircraft carriers have the right to be anywhere as long as they stick to international waters. But as soon as a plane leaves the deck, that's somebody's FIR.
Granted they can fly low, or even know where the radars are pointed. But that's not good for exercises and other missions. Do they coordinate, ask permission, pay a certain fee, or just simply show up. What about clandestine missions?
I've also seen before on Jeppesen en-route charts rectangular areas marked as air refueling corridors, if my memory serves me well, such example was near Malta. Same question, how does that work?