The encounters function as a patrol would, only often they remain static, staying until you leave the area. Here are some ideas.
Nomad Camps:
A small collection of desert tents, offering basic items for trade. Perhaps you'll find someone willing to join you here, perhaps you'll find they'll go hostile (small chance) if they see you are very well off. Perhaps tribals occasionally, perhaps refugee's, or deep desert dwellers etc.
Water Hole or Rare metal find:
Like an oasis only its a temporary spring or rare metal deposit, its only there for a short while. A cluster of bandits, individual looting opportunists or civilians from a random faction spawn there with it.
Caravans/Pack animals.
Either destroyed or killed by bandits (with some bandits still around), or damaged and unable to move their wagons/animals at your mercy.
Funeral mounds:
Either a service still going on, or a lone casket laying around, pyre's burning and banners held high (in keeping with the chinese funeral theme.) - Random faction or just civilian.
Refugee's passing through. - Random faction or civilian.
Cave (a hole in the ground), what's inside? Those who can't show their face in the light of day?
Sandstorms, or dust eddies avoid them!
They might occasionally begin to move 
, with this physics engine that would be fun.Slave Train - Caged Prisoners
A cluster of disease carriers, bandits, cannibals, slaves, (random faction prisoners) for sale or for execution. Either you can buy them, pass on by or free them.
Lone wanderers (If you like make them heroic/infamous names from a list, which you can bounty hunt)
Just like the player, small groups not belonging to any faction, with no history but their journey. Neutral/Hostile or Helpful - Random loot/strength
*Looked through the suggestions list but didn't find this specifically covered.
