Are you sure that the relay is what is going out. Have you cleaned the battery posts and cable clamps and made sure that they are clean and tight. If they are corroded the result will a lot of the time be a clicking of the starter. Same if the battery itself is marginal or is not receiving a good charge from the alternator.
It could be that changing the relay is temporarily 'fixing' the problem by your juggling connections.