Clearly, Muggles do leave the scenes of magical encounters--to take the most obvious example I can think of, Dudley goes home with Harry after they were attacked by dementors. The Ministry knows what happened because of Harry, being underage, still has a Trace on him to ensure he does not perform unauthorized magic. Without his Trace, the Ministry probably would never have learned of the incident, much less located the Muggle who witnessed it. The average wizard, however--underage or not--would not stay near the Muggles he or she had performed magic in front of. And the Ministry seems to only be aware of magic performed in front of Muggles if the magic was especially grandiose or the Muggles especially disturbed.
Remus Lupin's parents offer a good example of a Muggle-witnessed magic situation that the Ministry never discovered. Lupin's mother, Hope, was a particularly sensitive Muggle who realized that something was watching her as she walked through a forest. It was a Boggart, and it appeared like a large, angry man to her. Lupin's father, Lyall, heard her scream and used a nonverbal spell to force the Boggart away. Hope did not understand exactly what had happened for quite some time afterward, but Lyall had certainly performed magic. The Ministry, however, seems to have been unaware of the incident, at least initially. (When the story would really have come out is when Lyall and Hope put a Boggart on their wedding cake. As they were getting married, however, I doubt the Ministry would have cared. It certainly wouldn't be the last piece of magic Hope saw.)
Evidently the Ministry has a division (which, as far as I'm aware, goes unnamed) dedicated to dealing with Muggle witnesses of magic. Presumably wizards in that division have to have good detective abilities as well as a strong command of Memory Charms. Some cases, like the time Harry blows up his aunt by accident, would be fairly straightforward. Others--like the time Death Eaters blew up a bridge--required the Ministry to track down multiple Muggle witnesses and modify their memories. Since witnesses of most magical crimes would probably speak to the police, keeping an eye on police records would be one of the easiest ways for the Ministry to find Muggle witnesses. Keeping an eye on psychologists' offices or hospital mental wards would be another, since many Muggles, upon viewing magic, would think they were hallucinating and go for help.