Put an oil pressure switch in the ground side of the relay's coil circuit. This will keep the fans from coming on till the engine has oil pressure and you're less like to forget to turn it on as it's automatic.
Again, I reiterate, the contacts inside the starter are likely the culprit. I linked to a replacement set above. Cheaper than a new starter.
I have been working with Denso starters for over 30 years and I can tell from the symptoms it has NOTHING to do with the contacts. The starter would click and not start every time. His car is cranking slow so the contacts are completing the circuit like they are designed to do.
As far as the OP's thought on heat soak I have seen these starters so hot the decal melts off and they still start the car. I run an 11" flywheel and the starter in my Savoy is actually almost against the starter and it cranks perfect.
Gus
