I'm not an adventurer but I really like to explore, discover new sights and sneak in front (errrr.... well, make a big circular detour around...) of deep red mobs.
I feel that it would be a nice role-playing trick to give a small amount of XP whenever you enter some zones for the first time and move around in it for a while (not just staying at zone border of course).
This could be a nice, friendly way to say that sight seeing is also a fun part in AO. I don't see this being abused if it's only granted only once per character.
Of course walking for the first time in Newland desert or Mort shouldn't be rewarded in the same way.
As a better alternative an Anthropoligical Society Board could be created. It would work like Missions Boards, only that you it would collect tokens if you stay long enough in some zone of the games. Some minor buffs could then be granted after collecting enough "wilderness" tokens (speed buffs as you can imagine, ...).