Sound's like the ring gear on the flywheel is worn. The engine tends to stop in the same place when it's turned off and this area of the ring gear gets chewed up over time by the stronger metal of the starter gear. If this is the case, you will still have the problem after swapping out starters. The ring gear is a press fit and it can be taken off the flywheel with heat. You can flip it and reposition it so that "fresh teeth" will engage the starter gear or you can replace it with a new ring gear.
One of the nice things about the foot starter is that few of today's car thieves know how to start the truck.
