The exploit still exists, however...
I'm still curious to know your ideas on the rewards, though. I've thought about it before but kept running into the issue of capping the player to a certain level per major plot point. They could try adding interesting sub-plots tied to certain random encounters but they would only be able to do so many of those. In general the encounters would be formulaic, right?
I imagine that, especially on subsequent play-throughs, the encounters would feel like they are getting in the way if the rewards aren't satisfying enough or if you've already encountered all the unique encounters.
Standard rewards. A DM may throw a random encounter in every other game session or where appropriate. Let's say an encounter like this would reward your party with 200 XP at level 2. Split 4-6 ways, that's only 30-50 XP per character pet random encounter.
So go ahead and try to exploit. Roam around for hours and encounter maybe 3 or 4 random encounters during that time. Maybe you'll level up eventually.
Again, the point is Random Encounters should not be frequent. Average chance should be maybe 5% of having a random encounter - like rolling a 96 or higher on a 100 sider. Make the check every 2-5 minutes of gameplay or just at certain points.
So, for example, you step into Moonhaven. Game secretly rolls a 100 sider. It gets a 35. No chance encounter. Maybe another trigger point is Risen Road. Game rolls a 79. No chance encounter. You enter the well. Game rolls a 98. Chance encounter. Spider swarms attack.
In some areas that are really hostile, maybe chance increases. So, in hostile gobbo camp, chance is 10% - 91 or higher. Every 2 minutes, a secret roll is made because the place is on alert. You killed Gut or something. Game rolls 20 times, no roll is 91 or higher. You just spent 40 minutes prowling around with no random encounters.
So sure, you could try to exploit it, but it should occur so infrequently that doing so would bore the crap out of you. The point of random encounters is variety and spontaneity. It isn't to bog the game down or to be used for grinding.