3) What I'm asking is - does the ability make sense?
Does it really make sense that there are entities out there - who are not true heavyweights by any means - that can take the entire nuclear arsenal of the world to the face and not just survive but entirely laugh it off?
Does it really make sense that if the entire White Council worked together on the most potent Heart Exploding spell in existence, spend weeks and weeks sacrificing humans and going full crazy-on black magic to get into the 4 or 5-digit range as far as shifts go, creating a spell powerful enough to wipe a country off the map, a freaking Ogre(not a heavyweight by any means) could just shrug it off?
To answer the two "Does it make sense?" questions. Yes, it does. Compare it this way, if you are made of fire, does it make sense for you to be able to withstand a similarly powered column of fire? same answer. You may not like the existence of those creatures, but it does make sense.
The next question to ask is: Does it make them more powerful against those things as well? Yes it does. If you are immune to magic and all that the wizards have is fireballs to throw at you, you should win. Just as a creature of fire should handily beat someone only armed with a flamethrower.
If that's true then you need to ask the last question: Does it break the game? I remain unconvinced.
Combat does not have to simply be direct fireballs and physical attacks. There is much much more to it, and physical immunity only prevents that direct confrontation, it does nothing to stop every other method of interaction available to the players. Social combat, Mental attacks, physical aspects that are tagged, and invoked. Throughout mythology there are plenty of creatures that are just flat out immune to X, why shouldn't they be modeled that way in the game?
Physical immunity is a very specific very powerful ability. As a GM you should limit its use, but that doesn't make it a bad power. Shapeshifting, Glamors, even Thaumaturgy all have the potential to be game breaking when used and thought of in very specific ways, why shouldn't physical immunity? It exists to model those few creatures that are really and truly untouchable, and for those creatures I think it should be there. It is ok to force the players to panic, its ok to put them up against something that requires lots of creative thinking, and maybe even forces them to run away the first time.
While a GM should try everything they can to answer "yes but" there are times when "no" is the right answer. "Can I beat him into a pulp?" "No, but you could trap him in iron chains" is just as good an answer.
*Edit: And Belial just barely beats me to the punch with exactly the same thoughts.