I don't know the answer, but those who could help you would probably want to see the schematic of the FM transmitter. The receiver works well when not receiving from the FM transmitter?
You didn't say whether the supply was a switcher or not, but the context of your problem statement indicates that the problem may only exist when that power supply is used. If the noise is only present when the regulated supply is used, I'd suspect the supply.