Starter problem

I am having a problem with my starter that has me stumped. The starter will work perfect for a while then just stop working and going click, click when I try to start the car. I have replaced the starter relay twice, pulled and tested the starter ( worked perfect) even replaced the starter with another that I have in stock, and the same problem keeps happening. Please help me as I am lost!! Also I checked and cleaned all the connections for the entire circuit. What else can I look at?