OK, So I decided to inspect the relay. Nothing remarkable, a lot of dielectric grease on the prongs. One prong looked a bit funny. It had a faint rainbow hue to one half of it. The same kind you see on conductors that have been arcing. I cleaned all of the prongs up with contact cleaner, then replaced the relay and used electrical tape to secure it in the receptacle. Finished by wrapping the whole relay with tape. Have started about 20-25 times since. Not one click. I was at the point where every 3rd time or so I was getting the click. It appears to be fixed. I will report back if that changes. Thanks Pete!