The way I was taught to check for proper gear mesh is as follows:
1) Disconnect the main starter power wire at the 24V buss bar on the firewall, but leave the solenoid actuator wire connected.
2) Remove the inspection cover from the tranny
3) Crawl under the truck with a paper-clip
4) Have a friend, spouse whatever, turn the ignition key to the start position
5) If the bendix gear is properly spaced in relation to the ring gear on the flex plate, then you should be able to slide the paper-clip between the peak of the bendix gear and the valley of the ring gear. If not, then add or remove shims until the spacing it correct. I believe the manual will actually tell you what gauge of wire to use if you want to get really technical.
Does your starter have the brace on the back of it that attaches it to the engine block? If not, you run the risk of breaking starter bolts, the nose-cone, etc... It can also lead to bad tooth alignment if not properly torqued.
Also, as JB said, check the teeth on the ring gear. If they are worn excessively then you will have too much lash in the gearing and a new starter will do nothing to fix it. I had to replace the flex plate on my 1009 when I got it because several areas of the ring gear were badly worn.