I stopped using random encounters sometime back in 3E.
What I use now are "consequences" encounters. In dungeons, since I generally know what creatures are in each room, a general idea of routes they might take from area to area and any patrolling they might do, if the party encounters something unusual it's because they've either attracted attention or enough time has passed that the occupants may have shifted for one reason or another.
In the wilderness, I have pre-planned encounters ready. Less than half are combat encounters and may include points of color, mysteries waiting to see if the characters are interested in investigating or odd interactions or obstacles that may or may not be related to the ongoing story.
An example of a series of wilderness encounters I ran:
- The first day out of town, it rains the entire day. If the characters brave the wind and rain, they have to contend with wet gear, catching chills and finding a dry spot to encamp at the end of the day. The next day, they find they have to ford a swollen river and the local ferry is unwilling to run his boat across the rapidly moving river that is littered with debris from the previous day's storm.
- While on the road, a Storm Giant comes up the trail. If approached by the characters, he reveals he is a wandering merchant selling valuable wares he himself has crafted. However, instead of trading for coins, he will only part with his goods if characters can solve his riddles or tell him a worthy (and epic) tale - though he won't inform PCs of the latter unless asked.
- The party comes across a broken merchant's wagon, scorched by fire. If the party investigates, there are bandits hiding nearby who attempt to mug the players while they are picking through the wagon's goods. If possible, the bandits attempt to capture and ransom the characters back to the town they came from. In truth, the bandits are hoping to catch a VIP they expected to be on this road, but the PCs will do in a pinch. Possible complication: the VIP the bandits were hoping for shows up while the PCs examine the wagon (and they are accused of stealing), or after they have been captured.