Since walkers or similar gravity-obeying skills have their foot in the floor, the general rule seems to be that ohnoing occurs if and only if the foot is inside terrain.
That's a logical approximation, but as far as the PC version goes, it really is based purely on the action the lemming is performing at the time and not so much the terrain. The actions that prevent transition to "oh no" includes falling, floating, drowning, and maybe one or two more related to dying that I don't remember off top of my head.
In particular, you can observe the following on PC Lemmings: assign exploder to a digger such that at the time his countdown reaches 0, he is not directly standing on any terrain (possible because diggers can continue digging as long as there's some terrain at its "sides" so to speak). Something fun happens: it will transition to "oh-no", but because he's not directly standing on any terrain, he will fall down during his "oh-no" phase until he lands on something or explodes.
