Have you watched the amp when this is occurring?? If not, watch the power light and see if it's flickering on and off.
Also, play like a 50hz or 60hz sine wave, unhook the subs and stick a DMM on the amp's outputs. You should read a constant voltage.......if you don't, then you know the problem is the amp or somewhere prior to the amp (like the deck's RCA outputs). So, the next thing I would do is unplug the RCA's from the amp and stick the DMM on them. Play the sinwave again, and you should read some constant voltage amount. If not, then you know the problem is the deck's RCA preouts. If you do read a constant voltage, then you know the problem lies at the amp.
Or, if that sounds like too much work.....swap another amp into your install. If the new amp plays fine, then it is very likely that the amp is the problem. Either that, or something was making a very poor connection (but, you said you eliminated that).