On the 4e forums the subject of random encounters came up. Most complaints really came down to encounter speed in 4e, or just hatred of random aspects in the game.
Random encounters can work great, but remember you are rolling for 'wandering monsters'. If used correctly this adds flavor and doesn't necessarily lead to combat.
In B/X D&D, movement as you might recall was a little different. There was the combat round but also a unit of time called a 'turn'; this is 10 minutes. Your speed in an encounter, say you have speed 6 on your PC, that is 1/3 of your 'exploration speed', or how far you can go in a dungeon in a turn (10 minutes). This assumes you are kind of being cautious and 'mapping' where you are at. So, say for a 4e PC w speed 6, your exploration speed is 3*6 or 18 squares
Any encounter is assumed to take a turn even if it doesn't; the rest is made up by the short rest or looking for treasure or what have you. Any time you disable a trap, that takes a turn. Stop to work on a stuck door, takes a turn etc. and anytime you have a PC move 18 sqrs thru a dungeon it has taken a turn. In B/X, you had to rest once every 5 turns, or 10 minutes of every hour.
Then you say ok, every so many turns, say 3 or 4, I will roll for wandering monsters. Roll a d6, and a 1 (or a 2 if you want more to happen) means they encounter wandering monsters.
Now remember in old editions a monster was really just a blanket term for anything you came across; in 4e it is more accurate to say 'roll for random creatures'. You can have memorable, flavorful random 'encounters' that dont all have to be combat based. There is also some cool random flavor. Here is an example table.
Roll for wandering creatures once every 3 turns.
A roll of 1 on a 1d6 indicates an encounter. Then roll a d8. If you roll the same thing twice, reroll it.
1. 3-8 Eladrin explorers looking for a relic
2. 5-10 Gnomes carrying the carcass of a large creature
3. A sleeping (snoring) adventurer lying in the hallway
4. A large swarm of bats flies by; the walls are covered in guano
5. 2-12 giant rats feeding on dead bodies; they scatter when seen
6. A woman tied up in a corner with a gag over her mouth
7. 5-10 rot grub swarms gestating
8. 3-10 monks meditating in front of a strange image on stone a wall
If you really want to kick it old school and test your ability as a DM to improvise, you can roll the reactions of intelligent creatures randomly.
Roll a d6
1. Run from the pcs/scared
5. Beg the PCs for help
6. Act friendly and ask to join PCs, then betray them first chance
This is literally just off the top of my head. Hopefully it gives you some ideas on how it could add a little unpredictable flavor to your game.