The starter motor needs much more amperage when hot. Since the symptoms are the same for both starters, I am leaning toward cables, connections, fuse links, and battery. The ignition switch is also suspect here, esp with rapid key cycles and it works. The switch can be adjusted on the steering column, or simply may just have badly worn arched contacts. When cranking the distributor is firing the spark plugs, and drawing current. It maybe that firing of the plugs is enough resistance to over come the current flow resistance issue. All this is just an area that needs to be tested and proved good, if it is all good then my next step would be the distributor and or the ignition control module, even the pick coil can cause random driveability.
Is the battery a side or top post? Cables are original, replacement, have had ends replaced ? Age of battery ? Voltage at battery when resting and when problem occurs ? What is the condition of the wiring at the starter, when you replaced, did anything looked melted, or have replacement terminals ?