Maybe the level generation algorithm could break down at deep levels, generating "wilder" setups. After all, an "impossible" room layout can be just solved by leaving and re-entering. So why not having things like rooms without doors, corridors that run in circles without any rooms, stairs generated in corridor, or at very deep levels simply random scattering of empty squares and walls?
Or, maybe, the various level elements that are missing from ID (herbs, altars, shops, etc.) could start to appear beyond level 200 or so -- deep enough to not make ID an "easy source", but available for dedicated infinity diver (darn, now I want a game mode where you can only go through ID, but have no background corruption -- essentially unlimited-time dungeon. Reminds me of Ancient Cave from Lufia II...)
Other weird things at low levels:
Unique monsters -- like artifact guardians but without artifacts
Absolutely anything could appear, including elemental grues or jackal daemons