Lots of post about random encounters in the OSR bloggosphere this week. My 2 cents? Random encounters shouldn't be that random. Certainly in the outdoors it makes sense to have some tables for what sorts of creature might randomly be encountered outside of a lair, but in a dungeon great care should be taken in designing wandering encounters or patrols. I know that the mysterious wandering, random monster fits into the idea of the "Mythic Underwold", but I like a certain level of verisimilitude in my dungeons. If there is a wandering encounter, why is it roaming about? Where did it come from and where is it going? How will it react to the party, and how does it fit in with the rest of the factions in the dungeon?
Some of the best dungeons do an excellent job of providing a realistic wandering encounter table, such as Paul Jaquays' Caverns of Thracia. Each encounter is either part of a faction within the dungeon, or an unintelligent creature that one might expect to find living in the caves. On the other had you have The Sinister Secret of Saltmarsh, which has goblins on the wandering monster table for the haunted house. Why? There are no other goblins in the house, and no explanation as to why they are there. Unless they are working with the smugglers they have no place in the adventure.
"Random" encounters should be carefully tailored to fit the environment. This can take a bit of time if you have dungeon with a lot of history to it. On the other hand, if you are doing an old fashioned hex crawl through the wilderness you can probably do just fine with the standard tables in the MM or other such book.