i too, have run into bad battery cables as you described. on both the positive battery cable, as well as the solenoid to relay wire.
anytime a hot start issue is had, the first thing i encourage is to check for voltage drop on both of those wires, then go from there.
this mostly occurs from using those "bolt on" battery cable ends [did i ever mention i HATE those things ? ] which invite moisture to creep into the positive cable, causing corrosion inside the cable you can't see.