My car dealer was clueless and my internet searches were fruitless, but I've finally fixed the issues I was having with my driving music. It was all Apple's fault. In the hope that this reaches someone else with the same problem, I'm posting my story here.
I have a large library of pop music of various genres on my iPod, and I usually listen to it in random mode. It was working fine that way via the headphones. But my new Mini Cooper comes with a sound system that I can plug the iPod into, simultaneously powering the iPod and providing a digital feed of music to the car sound system. It shows me what it's playing on the car display, and it allows me to control the iPod from the dash or (for simple things like skipping to the next song) from the steering wheel. Much nicer than the usual auxiliary input jack. I'm guessing that some other car makes, especially BMWs, also use a similar system.
The problem was, about half of the time my car stereo was displaying the wrong song title. This wouldn't be so bad, but it was also getting other bad metadata (in particular the length of the song), causing it to cut the song short or run long into the next track and then cut that short. I was thinking maybe it was a firmware bug in the stereo that that would need me to take it in for an upgrade, or a bad line in the connector cable, or something. But no. This week, I tried reformatting the iPod and reloading all of its music. Now it works perfectly. So I assume some internal index on the iPod (used by the digital connection but not when I'm on headphones) had somehow become corrupted, that iTunes never noticed the corruption, and that reloading it rebuilt that index from scratch in an uncorrupted form.
In any case, the short version is: car stereo showing the wrong song title? Reformat your iPod.