How many people actually get killed in Lost Highway and in which order?

Laurent - Renee - Andy?... 

The one scene in the film which looks totally realistic is when the cops are searching Andy's house after the man got killed. And if so, then Pete killed him indeed (fingerprints) and he was - at least temporarily - a separate being from Fred Madison.

And Dick Laurent is dead, isn't he? Fred killed him before killing Renee, I would say, and when he told Andy at the pol party that D.L. is dead - it was true at that time IMO.

Putting the two above mentioned guesses suggests that the time went back around the moment when Pete turned back into Fred...
as if: Fred couldn't after all become a new being so he had to come back to his old self

But does it make sense? Not wholly, because if Pete had killed (well, helped) Andy after "that night" of somehow changing personalities with Fred, then he would also have known Mr Eddy at the time when he (Eddy/ Laurent) had already been dead...

Perhaps Andy never really died?

Bobi 1 Kenobi

B. Beware
O. Of
B. BOB 

Trying to rationalize a David Lynch movie is a common mistake. It seems pretty clear to me that the entire movie is set in the mind of Fred Madison right before being electrocuted to death for murdering his wife and her lover. I imagine he also killed Andy who was working with Dick in some way (maybe making porn movies with Renee in them?). He tries to go back and relive his life, but that falls apart as he is constantly remind of what he has done (reminded by the Mystery Man, who represent some part of him). After he remembers he tries to escape into another life, but that just turns into a new version of his old situation... he cannot escape the guilt of what he did. The narrative in the movie only makes sense according to dream logic.... as do most Lynch movies. I think this solution explains a great deal of the film, but most don't like it because it makes the whole thing so simple... Anways that's my take on it.

PS: I just had this thought... maybe the Mystery Man represents the deed of the murders (I can't think of a better way to put this)... that would explain why he's at his house, why he reminds Fred of the murders, and why he shoots Dick, why his face replaces Renee's.... it makes a lot of sense that way...

That god damn trailer's more popular than Uncle's Day in a whorehouse!

 I think your theory tallies very closely with my own. Certainly the bit about Fred awaiting execution is exactly right, in my opinion. Hence the mystery man's little speech about "In the East, the Far East...". In my interpretation of the movie, Mystery Man is Fred's Superego - trying to make him finally supress his Id (Mr Eddy) and accept his crime. I also think that, in "the real world", Fred killed Laurent, Andy, and Renne, like you said LWAPOM. I think the Mystery Man probably looks exactly like the key witness in Fred's trial, the one who got him put away. I suspect that maybe CCTV also played a part in Fred's arrest and conviction.

I think that Mr Eddy represents the Id because of the tailgating scene, coupled with the anecdote told by Michael J. Anderson on the Twin Peaks Season One Extras. I believe that this is David showing us what he would do if he didn't have that voice in his head (the Mystery Man) telling him not to.

I would also say that the first part of the movie isn't neccesarily a dream, but maybe just a representation of what is going on in Fred's mind as he lies awake, unable to sleep. The second part is the dream he has after being drugged up by the prison doctor ("you'll sleep now.")

"Every day holds a new beginning and every hour holds the promise of an Invitation to Love." 

That god damn trailer's more popular than Uncle's Day in a whorehouse!

I like that a lot!

In fact, rather than a dream or a trance, we should probably be referring to it as a psychogenic fugue, since Lynch and Gifford both seemed to like that idea, even though they didn't have it mind when writing.

I found a good quotation which helps explain my theory about the characters being Freudian personality factors: 

(the personality is) "...basically a battlefield. He is a dark-cellar in which a well-bred spinster lady (the superego) and a sex-crazed monkey (the id) are forever engaged in mortal combat, the struggle being refereed by a rather nervous bank clerk (the ego)."    -Don Bannister

So as I said, the Mystery Man is the prudish superego, while Mr Eddy  is the sex-crazed monkey! And Fred/Pete is the ego - but instead of trying to mediate, he's still running away, showing the flaws in Freud's ideas (I think David is known to be more sympathetic to Jung's ideas). Here's another quote, expanding on the different role of each of the three factors:

These theories all make a lot of sense but I'd just like to add one part.  I always felt that the most important line in the first half is when Fred gets asked about why he doesn't like video cameras, and he says something like 'I like to remember things my own way... not necessarily how they happened'.  So, I think that the first half is him reconstructing the events leading up to him lying in his cell, but trying to implicate mystery men and complex surveillance plots in Renee's murder rather than just facing the fact that he chopped her up one night in a jealous rage (perhaps brought on by Renee's dealings with Andy).

BTW - I really like the mystery-man-is-the-deed theory.

I am likely to miss the main event

If I stop to cry or complain again.

So I'll just keep a deliberate pace,

Let the damn breeze dry my face.

I totally agree. I think DL is all about putting key lines in his movies. To name some of them:

Blue Velvet: "It's a strange world." (well, that's a bit dull. "I guess there's trouble 'til the robins come" would be an interesting choice too, I think.)
Wild at Heart: "This whole world is wild at heart and weird on top."
Lost Highway: "I like to remember things my own way. Not necessarily the way they happened."
Mulholland Drive: "I just came here from Deep River, Ontario, and now I'm in this... dream place!"

And yeah, my two thumbs up for the Mystery Man -deed -thing as well.