I have had a problem like yours. I originally thought that it had a pattern of not starting only when it was cold, but then it began just clicking at completely random times. I replaced the starter with one I had laying around, and it worked fine for the first start but then back to the random click, no start. Then a few days later it wouldnt start at all. It turned out the only problem was that the terminals on the battery were corroded. They were not visibly corroded but once I popped them off there was a little bit in there, just enough I guess for the terrminals to not be able to carry enough amperage to the starter. (just a free thing to try if you havent already)