Wow, well I have never had a starter issue so I can't say for sure.
So I will just throw this out. When warm, have you tried using a screwdriver to jump the contacts on the starter solenoid? Just to rule it out? Jumping it removes the solenoid totally from the equation. It may be that it is starting to go out and is not operating right when the engine is warm, since the starter sits in that heat.
Maybe the solenoid is working well enough for cold starts, but not warm. Engines start better when warm, usually, but motors are more efficient when not hot.
Like I said, never had a starter issue but if I did, I would try this. Just to rule it out, if nothing else.
The ride IS the adventure. The destination is just to get gas!