This is a common problem with starters. It means the starter solenoid is going out. This essentially a magnet that pushes the starter gear to engage with the flywheel. On older vehicles this was replacable seperately from the actual starter motor. Now it is all self contained and you have to replace the whole unit... not a bad idea, because once the solenoid starts to stick the starter motor prolly needs new brushes etc... I advise shopping around and getting a lifetime warrentied one (I know Shucks does these - prolly the only kind of parts I recommend buying there!) but I tend to keep cars for a while!
The missing teeth thing is much less likely... although I'll admit it can happen, but usually involves missing teeth on the flywheel as well. Not a good thing!
----
Just noticed bassthrive's post, and yes low voltage (bad battery, bad connections etc..) can do this as well. ALWAYS make sure you have enough juice FIRST THING if you ever have starting problems!

Sometimes I forget to mention stuff like this because out here in the hills we learn this shit in 3rd grade!