It is a heat related issue. It might also be the battery but not likely. I would check the cables going from the battery to the solenoid and then from the solenoid to the starter. If they are brand new they might be ok. Typically they came undersized from the factory, and once they have aged a little bit, they have excessive voltage drop.
The cables are not likely the only problem. With your discription I would bet dollars to donuts that your starter is faulty. When it doesn't start are you getting a RRRRRRRR, spinning but not as fast as it normally spins? If so, starter is puked.
Leaving batteries to sit does not charge them back up. What you have experienced is equalization of sorts. When you take a high load off a battery it will appear to recharge itself. i.e. If you put a draw on a battery it will go down to say 8 volts. Then when you stop it might immediately go back to 10volts, then slowly climb back upto its correct power level. This happens in about 10-15 minutes. It is not recharging but sort of redistributing its power. power it already had.
If you place a battery in storage that is not 100% fully charged, it will actually discharge and flatten itself over time. (1-6 months)