An experienced or spoiled player doesn't need to explore the wilderness, use scrolls of Magic Mapping, Detect Monster or Detect Item. "The stick of truth ? Enter XYZ, teleport 8 west, 35 south and talk to the Foozle."

This simple idea could change it. Blup's mom could be spawned somewhere in a radius of 5 squares. Darkforge treasure vaults can be moved a few squares left or right each game. The grave of Griff can be in some random location in the final chamber (I'm not sure Griff doesn't start standing on it, but I managed to teleport on top of the grave after waking Griff). Ancient Chaos Wyrm and Chaos Archmage can be in a slightly random position (within a distance of 3 squares from the altar).

I'm proposing this to make the game less formulaic. Just make it so these locations can't be played with your eyes closed.