I’ve scoured six first-level dungeons, now, and two second levels. He’s evidently gone on vacation. Or is this typical of the guy?
The chance to find him isn’t incredibly high, so while it’s not probable, it’s possible to not see him after 8 dungeons.
I was under the impression that he has a higher chance of appearing in deeper realm levels. I’ve been hanging around in realm levels 7-16 recently and I’ve seen him in almost every other realm I visited. I can’t remember ever seeing him in the lowest levels, but that may also be due to my lack of progress with the nether creature castle quest back then.