Is the small terminal on the solenoid tight? Wire and the terminal post itself? Cause if it isn't, the solenoid won't engage and pull the bendix drive out to contact the flywheel.
My 99 5.7 Burb, when my family got it, had issues with starter hitting bad places on the flywheel. The cap and rotor had carbon tracking inside, and sometimes that made the truck try to fire 2 cylinders simultaneously. Eventually it got bad enough that the starter had to be replaced multiple times. The last time, the starter end frame/nose cone was in multiple pieces.
Replaced cap and rotor, starter and flywheel. No more issues for several years. Then in February of last year, it developed a hot start issue. That was rectified by cleaning the starter, replacing the long positive cable ( the one that goes across the fan shroud), cleaning the other cables and connections, and tightening the small "ignition " terminal on the solenoid. The wire from here goes to the ignition switch, and activates the solenoid electromagnet to pull the bendix arm out and throw the bendix gear into the flywheel teeth. Good grounds and clean and tight connections are important on these trucks. Even a very slightly loose battery cable bolt can create problems.