Batman? wrote
ADOM (My personal favorite of the rougelikes) has permadeath and random overworld encounters that are handled very well. they have the difficutly scaled by location (how far you are into the wilderness from the stasrt of the game) and by game time, so early on in the game you get goblins/kobolds etc, but as the game clock runs the monsters get more difficult. it occaisonally causes an early charecter to get killed ,but in general adds a nice flavor to the game.
I've always felt IVAN was characterized by the dungeons with their mix of random enemies and design as well as static additions that presented new problems or possibly new solutions (though certainly not without cost). Random encounters out in the wilderness I feel would break the feel of that and since the 'real' part of the game takes place in the dungeons anyway, I don't think it would be a positive change. Also worth noting is that as the game is at the moment, the previous concern is irrelevant because the longest trip anywhere in the overworld is from the underwater tunnel to Attnam, and as the second longest trip is generally much smaller, unless you make random encounters really common there probably won't be all that many and thus it won't be able to make the kind of impression they do in ADOM. Though, really for me it seems like it will be more annoying and unfun than otherwise to have random encounters.