MY THEORY, after re-watching this and dissecating a bit:

I think the intro monologue kinda explains what's going on.
Here's my theory of what happened, chronologically (as much as possible), since I don't think the movie was based so much on time warps, but more on symbols and inner struggles:

- Richard is a serial killer since he was 16, when he developed a fixation for blondes, after meeting a girl he was afraid to approach);

- this time he meets Gina in Vegas, and falls in love;

- the routes 93 and 95 are just symbolic, they represent his inner struggle. He wants to kill her (route 95) but he also loves her (route 93) and goes back and forth, not sure which path to choose;

- the man at the diner is the voice of his scarred (noticed that on his cheek?) conscience, telling him to stay on route 95 (LOVE) and "take care of that fresh wife of yours" this time.

- as they stop and he checks the map, he's upset because "we should be on 93 (!), but we're on the 95..." This dialogue doesn't make much sense since, according to the man at the diner, 95 is the road to follow, so where's the problem? The problem is that his dark side takes over and forces him to go back and search for road 93 - murder, which he can't find immediately because of his inner struggle - his love for Gina.
There's a subtle dialogue also, which only makes sense after you watched the entire thing:
Gina: - Don't tell me you're one of those "I never take a wrong turn" guys.
Richard: - I never turn...

- he murderes/shoots Gina in the desert, with the gun he found in her purse; it could have been there "for protection" because she knew that he was unstable;

- Gina is actually murdered in the desert. As someone here pointed out, her murder is hinted at when she dissapears from the grave site and suddenly appears next to him, in the car. That's clearly the beginning of his delusion.

- the rest stop being there is just part of that delusion. He pictures the place as he knew it at the age of 16; Gina wearing the black clothing symbolizes that she's already dead. She is later found by the Police, wearing the same white clothes she had on when they stopped at the grave site.

- their argument at the rest stop is symbolic, as he can't get rid of her image and memory. He tries to justify his actions/murder by accusing her of being a filthy woman. So is his search for her, the gun shots still echoing in what's left of the good side of his conscience;

- the watch ended up buried inside Gina's grave and gives him away;

- just to make this clear: by the moment he notices it's gone, he's already delusional at the rest stop, and Gina is dead.

- he finally becomes aware of the situation (him being given away by the watch) and flees, escaping the police;

- his alter ego looks at him, with regret: "I told him to stay on 95..."

- While fleeing in his car, his good side is talking to his dark side:
"I'm gonna find you... YOU've set me up!"

OTHER DETAILS:

- the blank map at the rest stop, showing "you are here" - in the middle of nowhere points out that there's no escape of purgatory.

- the cigarette. Good Richard doesn't smoke, while his dark alter ego clearly asks for one.

- I assume that the fight between bloody Richard and "good" Richard is also symbolic, not sure if it actually take place or not, as the events are clearly taking place while Richard in in purgatory. It's more about pointing out the struggle that takes place inside him when it comes to murdering Gina.