The KM PbP I'm in has so many dangling plot hooks that we have a list of stuff we need to take care of, and are sort of pinging all over the map, seeking out and taking care of pacifying various threats, etc. in addition to exploring new areas.
It almost feels like having a 'quest journal' in some online game, with so many different encounters scattered around that need dealing with, and, instead of a dungeon, channeling us from encounter to encounter, we are wandering around the countryside from encounter to encounter, with a better notion of what we are about to find behind any given 'door,' since we probably went in that direction specifically to deal with the rumored beastie(s) in that area...
A preparation-based class, such as a Cleric, Druid or Wizard, might find that pretty cool, as they can prepare specific spells with at least a passing notion of who the 'threat of the day' is going to be.
Encounters can be a bit bigger as well, as the overland travel / exploration doesn't generally include three to five encounters in a day, allowing the PCs the freedom to unload their biggest guns in every fight, without feeling the need to 'save something for the next room.' It could be a day, or several days, before reaching another 'set piece encounter.'
On the other hand, random encounters can still occur, and if the party has completely shot it's wad on the big fight, they might get pummeled...