Escorts are... there's a limit to them, of course (there are always and only nine), but beyond that I think there's some filters on when they can show up, at least in the early game. It's been long enough I've forgotten exactly what they are, but I think you'll only find them in the first... two dungeons, after the first one you go in to? Among the tier one dungeons (which are what you mentioned). Then they're a bit more free form amongst the higher tier dungeons, though you're incredibly unlikely to have not encountered them all before the dungeon prior to going east. Though I do believe it's possible, if barely so, for one or two to end up getting shifted into eastern dungeons. Just tremendously rare.
Also, you can go back up stairs once you start being teleported to the bottom, if you haven't already noticed. Escorts should still show up if they're slated to, iirc. If not, come back down the down stairs after clearing the level (if you're doing it from bottom up, that is). Think that may trigger 'em if the first go through didn't. Still, if you haven't found all nine before going east, it might be time to backtrack and do a quick jaunt down the dungeons* one more time.
*Though I do believe that only the "main" dungeons (barring sandworm lair and... maybe a couple other ones?) can generate escorts. There's also some racial stuff involved (the elves usually get one of the second level of their starting dungeons, ferex)