It sounds like your relay is sticking. The circuit that starts the relay is activated with the ignition switch but the wire going to the relay to run the fans is "hot at all times". Get a heavy duty relay from John Hervey (40 amps). Both fans take a full 22 amps at run (11 amps each) and nearly 40 amps to start them. That is a lot to take away from the starter circuit - especially if your battery is low or marginal.