Enemies that petrify your party for example, they don't add difficulty, they just force you to reload and prebuff before the fight. No one in BG1 or 2 ran around always buffed, they just mowed every trash mob encounter and when they inevitably died because some developer decided to drop a couple of basilisks or a demi lich around the corner, they just reloaded.
A way around this is to have dynamic mob composition on encounters, and add real feat/skill/item usage to humanoid monsters, instead of a single instakill/petrify skill that serves as a difficulty buff.
The challenge comes in preparation and resource management. Sure, it's a "prepare or die" situation unless you get really good at kiting, but considering you see Basilisks in literally two areas in the entire game (one expansion area) it's not like this is "cheap". You get
plenty of warning including the
frozen stone corpses of dozens of adventurers at the entrance of the area, and several NPCs even say "be sure to pack some protection scrolls if you head south." If you wander into that like an idiot, you deserve to get petrified.
I agree that they aren't the worst example of LOL UR DEAD kinda difficulty. Here's how I imagine Josh Sawyer would do it, though:
Instead of petrifying and insta-killing your characters, a basilisk would paralyze your characters and then attack them. With no way to defend themselves, the affected characters would take lots of damage, but in the first encounter with a basilisk, the non-paralyzed members of the party would probably succeed in defeating it before anybody was killed.
After that first encounter, a smart player would know to look for a way to resist this paralysis and would go searching for Korax the ghoul. If the player isn't smart, then he'll probably lose some already-wounded party members in the next basilisk battle.
See above. The Basilisks actually have one of the best enemy introductions in the whole game. It's nothing compared to the random mages who have preset spell triggers and contingencies and special scripts that let them break the game, and the only way to win is to learn their patterns through trial and error.