The implementation I have in mind works in conjunction with Ixi's pass some turns off level idea.

Here is how I would do it:
Upon leaving a level that contains a companion, instantly run the level you just left with the logic acting as if you're standing on the stairs, until the companion(s) die or end up next to the stairs.

Based off of how many turns that took to happen, after those turns elapse on the current level it then either places the companion on level (if in LOS, print a message similar to how companions show up in wilderness) or (maybe) print a message sensing loss if they perished.

I think this would make companions less of a headache with hitting 5 to make them catch up, or even when ones faster than you bounce one square away from you.

*EDIT I realise there's a flaw in this in that it elapses turns even if you haven't taken turns off level. I bet you could actually rewind the game though if it were coded in the right way, to overcome that.