Ya need to do a complete diagnostic regarding the battery itself exactly at the point the issue occurs! Let the dvom (or volt meter)tell ya what is going on!
Clean all battery cable terminations at both ends, along with the connection points. The battery terminals themselves must be "bright" and all traces of oxidation removed. Verify that the ground path is just as clean and proper gauge size as the "hot side. The battery ground should run to the engine, the engine must be grounded to the engine and frame as the ground for the starter is the interface where it bolts to the block.
When the starting process exhibits this issue, it is imperative that the starter current draw be measured, use an inductive (clamp-on) ammeter or dvom to do that, normal starter current draw cold or hot is in the range of 85amps>150amps in a single burst before the engine starts. Don't crank for more than 1o seconds in that test or the starter May melt down. And you must monitor battery voltage during the starter draw test in order to determine if the battery is ok.
