You may've already run the session, but I want to go a slightly different tack with this.
When I have monsters that the PCs are expecting or simply experienced with, I like to throw in a twist to the combat. See, I enjoy making PCs make tough decisions, both tactically and in role play. Rather than making the actual monsters bigger and tougher, I make the players make difficult decisions.
In the military, they call it "combined arms". You use two different weapons that cover for each others' weaknesses. For example, in WWI, they'd have machine guns laying down cover fire, which encourages the enemy troops to keep their heads down and stay in the trenches. Then they'd drop mustard gas shells on the enemy position. Mustard gas is heavy and flows down into the trenches, thus encouraging the troops to get out of the trench and make a charge. So they have to decide whether to jump up and charge the guns, or sit quietly and breathe poison. (Or, more accurately, hope like hell their gas masks are airtight and functional...) Or you set up a minefield, leaving a narrow clear path in the middle, and then set up gunners all around it. The enemy can come up the middle right into the teeth of the machine gun nest, or they can pick their way slowly through the mines while being sniped by at by rifles. You can get similar situations by combining tanks with air support or foot soldiers with cavalry.
So in this case, you have a basilisk, which encourages the PCs to close their eyes. The perfect compliment to that, then, is artillery units -- archers and wizards and such -- that require the PCs to open their eyes to target. Another good compliment is rogue-type characters who get bonuses -- like sneak attack -- for attacking blind enemies. Again, open your eyes and make a save, or keep them closed and get stabbed. Archer rogues are perhaps the nastiest backup unit you can come up with.
A second option is environment (if you don't really want to mess with allies and combined arms). Make the environment something that encourages looking. You might set the battle on broken terrain where a blinded character could stumble on uneven ground, or even walk right into a crevasse. Or you could go with a thick wood where the gaze weapon is crippled, and give the basilisk excellent Move Silently and decent Hide -- finding him by anything but pure accident will require you to be looking, but then you've met his eyes.... That's a lurker that doesn't require any sort of speed at all.
A third option, which you could combine with either of the previous two, is the previously mentioned idea of changing his gaze to something other than 'stone'. I like venomous eyes that inflict poison with a glance, myself, but it's up to you what you want to do. You could even do a "slow petrify" effect, with a poison that first slows, and then petrifies the victim if they fail the secondary save. A less devastating gaze attack encourages the players to just open their eyes and have at it, and deal with the consequences after.
That really makes closing one's eyes too good of a tactic. Yeah, lots of bites at +2 hurt, but considering each save is automatically 5% petrification chance, opening one's eyes is too great a risk in that fight.
