Very interesting set of symptoms.

Clarification: When you say that "rebooting" solves the problem, but then go on to say that in addition to rebooting, pulling it out of the sled and re-inserting it is sometimes required, what is your definition of "reboot"?

The reason I ask is that, for most people, pulling it out of the sled and re-inserting it is the way that you'd tend to reboot it. But because you make a distinction between the two, and because it might be an important symptom in the diagnosis, I'm curious what exactly you mean by "reboot" that's different than pulling it out of the sled and re-inserting it.

There are ways of rebooting it without pulling it out of the sled, and depending on which one you're using, it might help indicate whether the problem is a car-wiring thing or an internal-to-the-player thing. Another thing you could do is plug it into the AC adapter in the house, and listen to it from the RCA connectors. If the problem happens there too, then you can be certain it's not the car wiring at issue.

In the meantime, get us a boot log and a RAM test result, which might possibly help.