Vorpal Blade should always decapitate Medusa. When this happens, it produces a “Medusa head” comestible, which is a unique, unwishable item which could either confer stoning resistance when carried or, like in the myth, be used to stone monsters at range.

An alternative, to make it more broadly accessible, is to allow any bladed weapon used in melee to decapitate Medusa, and only her, on a critical hit (while Vorpal Blade will decapitate on any hit that lands).

Cockatrice corpses when eaten should have a chance of conveying permanent stoning resistance.

Skeletons should only have partial stoning resistance. If they would become petrified, their bones do petrify, which leaves them still mobile but slowed down, and unable to be cured by speed monster. (This does raise the question of what happens if you cast stone to flesh at the petrified skeleton - does it create a “meat skeleton” or just restore its ordinary bones?)

The messages “You feel less concerned about becoming petrified” and “You no longer feel secure from petrification” should be tweaked, since they don’t really read stylistically like other NetHack messages.

Artifact polearm of unspecified type The Ten-Foot Polearm. When wielded, it confers immunity to stoning from c corpses, artifact blasts, and special damage from bane artifacts that hate you, because “you don’t touch them with a ten-foot pole”.

Stone shield, a magical shield made of stone that provides stoning resistance, but is quite heavy.

Rock trolls are immune to stoning; not because they are made of rock, but because they already have an affinity with it.