MP3 doesn't really go as high as 44.1 kHz anyway. The first step in compression filters out audio above 18 kHz, so a 36 kHz sample rate would have been sufficient. But that's not really the problem anyway. FM is analog and therefore doesn't even have a sample rate. A sample rate is the rate at which digital samples are taken.
FM does have bandwitdh, as you figured out. But the 75 kHz radio bandwidth isn't directly equivalent to 75 kHz audio bandwidth. In fact, that's the whole point of FM. AM is the modulation type for which the correspondence is a lot easier, just a factor of 2. (That's because they send the same information both below and above the center frequency, for simplicity and quality - single side band radio eliminates that factor of 2 for a slightly lower quality). But this simplicity means AM has a low audio quality - best for voice. FM uses a more robust modulation (encoding) so that the audio amplitude becomes a radio frequency change. As a result, the radio signal amplitude isn't that important anymore. And it's that amplitude which is most easily disturbed.
Effectivey you get 15 kHz audio bandwidth out of FM - a lot better than the 5 or so that AM gives you. Still, you lose about 3 kHz from the MP3 signal. In your case, that's probably just one of the causes. The limited MP3 bitrate causes some distortion, too, as does the whole digital->analog->FM path. They all add up. The easiest fix would be to obtain better quality MP3's, or a digital connection to your car sound system.