There are two kinds, one that allow you to walk on water and the other allows you to walk on lava. I can't find any of them in either game. Where are they?

The fire walk scepter appears in levels 15 and 17 of Witchaven I, and level 5 in Witchaven II. In all cases they're placed in areas where you have to fly to grab them.

The water walk scepter never appears, as far as I know. If you edit one in with the map editor, it works like you'd expect, but it's not placed in any of the maps.