onelane,
If your truck still has the stomp starter, it is probably the original 6 volt starter being run on 12 volts. This is OK and common practice. If this is true, I would pull the starter and look at the mechanical linkage from floor stomper to starter switch. This can get worn and not allow the bendix to fully engage the ring gear.
While it's out, look at the ring gear with a trouble light and see what condition the teeth are in...do the same for the bendix. It might be a situation where it's worn linkage, and a worn out bendix.
Stuart