"This power is not necessarily absolute; plot-device-level threats still have the potential to harm the creature even if the catch is not satisfied (e.g. a nuclear bomb, the combined magics of the entire senior council, etc.)"
That's pretty much the same type of thing I was about to bring up: Being the GM, you have to understand that all powers as written in the book have at least a little bit of "wiggle room", where the Story's needs are concerned. It's probably a good idea to imagine that every rule has a "PS: this is subject to the needs of the GM and the Story; Don't be ridiculous with it," invisibly written after it.
As for Physical Immunity, I think it
can be fair, but only if the GM is mature enough not to abuse such a power. The Original Poster mentioned the possibility of a nuke, or the entirety of the White Council aiming a ritual at a character. I wonder, though, if they intend for this to happen in the course of their game? If not, then the question is moot. If you can only come up with improbable, ridiculously powerful things as examples, you're stumbling into the land of hyperbole.
As several posters have mentioned, the reason to choose Physical Immunity rather than Mythic Toughness and Recovery is because it fits the character you're making, the experience you want your players to have, and the story you're trying to tell. If you want a baddy who takes a licking, and keeps on ticking, but gets visibly worn down as the fight progresses, Take the Mythic coupling. If you want a villain that seems to be unstoppable, until you figure out his Achilles' Heel (Perhaps literally, if you have the players come up against Achilles), then he goes down quickly when hit with "the right stuff", then choose Physical Immunity. It's the
story that determines whether the power is appropriate or not, not just the Letter of the Law.
And if you are allowing Physical Immunity for a Player character, I suggest you have a sit-down with them regarding how you view the power, and the restrictions you will be putting on it, if any. Perhaps requiring an extension of the Catch, so that the character can be hurt by, for example, "Left-handed Sword attacks
and single attacks of more than 12 shifts of damage," would make it more palatable to both parties.