I ran a couple of immortal level games back in the day. I relied heavily on the setting for narrative (I played in Mystara) and the players were generally
- against the clock on some-unknown-thing-from-elsewhere threatening to destroy the multiverse
- investigating which immortal was breaking the rules to destroy some mortal country or institution
- tying up loose ends from their mortal life without being detected as the immortal they now are
Very often I would put them at risk by forcing them into avatars and running weird mini adventures, planes without magic so they had to get clever, or making the problem a diplomatic one, so they didn't have the ability to just roll to hit their way through the story.
The narratives generally unfolded as mysteries or gather games, so they couldn't just power through it.
As for time and space, the characters could go explore all kinds of weird stuff. Mystara had some strange space stuff going on.. the immortals all lived on the moon, and an area called Spillworld where the planes were pouring into space and could be seen from Mystara. There was also high tech stuff in Mystara, nuclear powered magics, ray guns and space ships were all there. You even could travel to Earth as an Immortal in IM1 (if memory serves).
I also made the characters interact with their churches and clerics in order to maintain or gain power, and they had to sort of keep up with the mortal world. I had an immortal that became the patron for a family so they kind of checked in on the different generations and once went and found their souls in the mortal afterlife.
As for random encounters, I never really liked them even at low levels. There's just something in my brain that has trouble working out the ecology of, say, a group of fairies wandering through an area where there was a group of giant spiders in the week before and whatnot... so whenever the characters encountered something, there was some rhyme or reason to it, often just adding to the theme or flavor of the story.
As for the rules, well... back then I don't think anyone really ran a straight-from-the-book campaign at any level. In decades of playing every week I don't think there was a game that went by without at least one fight over the rules or debate about how to codify some new situation. You can see this in the way AD&D published and applied random books on all kinds of weird topics. So when we couldn't find a rule, we just crowbarred one in and kept playing. It really wasn't until third edition where I noticed the rules were treated as sacrosanct.