I've had the same problem with my pioneer headunit.
Every thing you tried, I have tried as well. but still failed to fix the noise.
Until I used an inline power noise filter.
I just matched up the fuse rating to the headunit and bought the one closest to the fusing.
I used this one
http://www.sonicelectronix.com/item_38579_P.I.E.-NF-20.html
But here is a cheaper one But does the same exact thing, but looks better.
http://www.sonicelectronix.com/item_26831_Axxess-AX-ANR1000.html