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?)

There should be a method of fixing the speed of pets which have been permanently slowed and which have a high monster magic resistance. Either the wand of speed monster should ignore monster MR on tame monsters, or it should be possible to break a potion of speed on the pet to remove the slowness.

Ice devils should have a slowing attack, like they do in D&D. Most likely, this should be like a lichen’s temporary slow in EvilHack, rather than a permanent speed-loss like a shade or skeleton has. Free action could reduce or negate this.

Hellfire from monster casting, being inspired by Ghost Rider, should in addition to ignoring fire resistance slow the player down, since it does spiritual damage that reduces the victim’s will to act.

Add a dragon which has slowing breath (or convert the orange dragon to use it). The effect stacks with previous effects of slowing breath.