What about a certain type of random encounter that has specific impact upon the game world?
For example, each city has designated trade routes running between them. On these trade routes caravans travel back and forward between destinations. These caravans may be attacked by random mobs and you may have the chance of assisting them. The real world implications of this are numerous.
Firstly, a caravan that is attacked and not assisted will mean a shortage of supplies being delivered to its destination. This may decrease the availability of goods at that location and drive prices higher. Secondly, you could simply take advantage of the situation, kill the mobs and take the loot for yourself. Thirdly you could even attack these caravans yourself, essentially making you a bandit. This would make you wanted by authorities but would provide you with material rewards.
Another example may be smaller settlements being attacked by mobs. Each settlement would have its own militia to fend off the attackers however they may not always succeed. This could result in settlements being totally destroyed if no assistance is provided by the player.
A player might assist in defending a settlement, then pursue the attacking, let’s say goblins, back to their lair. This would then involve a dungeon crawl to destroy their leader and scatter their forces.
I think in this way, these kinds of encounters don’t feel like generic task based or combat based situations. The encounter would have actual implications to the game and provide you with the satisfaction, or grief, of your decisions within said encounter.
I’m certainly not proposing that this kind of encounter be the be-all-end-all encounter system, but it could be implemented to add more depth and value to the game.
Also, I think it would be a nice touch to have some encounters dependant on the game time. It may be typically unsafe to travel between towns by night for example, as bandits and highwaymen are more frequent. This would also bring more meaning to the day / night system.