This morning at church, I was talking to a guy who has several old cars. A hot-rodded 40's Chevy truck, a Corvair, a couple old VW bugs (apparently one of them can trounce alot of Mustangs)...
He said he had a car that, when the motor was hot, it would act like mine (would not/would barely turn over when trying to re-start the motor). It drove him crazy for a while, but then he put a new starter on the car, and that solved it.
He also said to try to shield the starter from heat as much as possible. The exhaust pipe on my car is maybe 2 or 3 inches from the starter motor.