Did you hook up an external crossover? I had the problem with my Pioneer deck with engine noise and ended up selling it, well not main reason why, but I thought I was getting out of audio......well I didn't. I ended up getting a Kenwood deck and some new componets and I didn't have any engine noise what so ever...........ahh, it was so nice! Then, I get tired of not having any bass and put the subs in there with amp and the external 3-way crossover in there. Well guess what, now I have engine noise out the whazoo! Well not that bad, but it is there. Ended up being my crossover, which still works, just has a bad ground in it. So just throwing it out there as it may be your problem as well.
I did that samething with you, grounding the deck all kind of ways, swapping out RCA's, taking all out and putting back in, moving wires from right to left, left to right. The one thing I never checked.............was my crossover............well ended up being it all along as I took it out and used the crossovers in the amp and it went away! Problem is my internal crossovers **** compared to my el Cheapo external 3-way, so hooked it back up and bam, noise is back. So investing in a new crossover.
Just trying to help.