This pit-fall of Challenge Rating is anticipated in the Dungeon Master’s Guide.
The DMG gives some guidance for designing encounters, and there is a sidebar on p. 82 that mentions exactly the problem you are describing:
In addition, some monsters have features that might be difficult or impossible for lower-level characters to overcome. For example, a rakshasa has a challenge rating of 13 and is immune to spells of 6th level and lower. Spellcasters of 12th level or lower have no spells higher than 6th level, meaning that they won’t be able to affect the rakshasa with their magic, putting the adventurers at a serious disadvantage. Such an encounter would be significantly tougher for the party than the monster’s challenge rating might suggest.
Essentially, this is just a known shortcoming of the Challenge Rating system. Challenge Rating is a pseudo-objective system explained in the DMG’s guidance on designing monsters. It is based solely off of the numbers in the monster’s stat block, and simply does not account for issues like the one you describe, which is why the DMG guidance cited above mentions it. This is just something you have to be aware of in encounter design.
The canonical solution here is to hire a priest.
The Player’s Handbook (p. 159) gives some guidance here, and suggests spellcasting services as a solution to a lower-level party being unable to overcome an obstacle like petrification:
People who are able to cast spells don't fall into the category of ordinary hirelings. It might be possible to find someone willing to cast a spell in exchange for coin or favors, but it is rarely easy and no established pay rates exist. As a rule, the higher the level of the desired spell, the harder it is to find someone who can cast it and the more it costs.
Hiring someone to cast a relatively common spell of 1st or 2nd level, such as cure wounds or identify, is easy enough in a city or town, and might cost 10 to 50 gold pieces (plus the cost of any expensive material components). Finding someone able and willing to cast a higher-level spell might involve traveling to a large city, perhaps one with a university or prominent temple. Once found, the spellcaster might ask for a service instead of payment — the kind of service that only adventurers can provide, such as retrieving a rare item from a dangerous locale or traversing a monster-infested wilderness to deliver something important to a distant settlement.
In one of the games I ran, one of the members of the 5th level party was petrified by a basilisk. At the end of that session, I had a conversation with the table about what they wanted to do about it:
Thomas: Okay guys, Chris’s character is petrified, which for the moment, is basically death. Now, Tessa’s character (the cleric) would know that the temple in the capital provides the kind of care that can reverse petrification, but they usually require some work to be done. So your options here are: Chris, you can just roll a new character, or, if the rest of you want to, you can pursue getting Chris unpetrified.
The party decided to try to get Chris cured. Upon arriving at the temple and talking with the chief priest, they were tasked with accompanying one of the temple’s paladins to consecrate a wilderness temple that had been desecrated and had a necromancer squatting in it. I used this paladin as Chris’s temporary character, and upon returning from the quest, Chris’s character had been cured of petrification.
So basically, no, you’re not missing anything. Some monsters present dangers that are not accounted for by Challenge Rating, but the guidance given in the DMG and PHB account for this so that you can design your adventures around such high stakes encounters.
