Your problem sounds like you have play somewhere, either in your axis or spindle bearings or could even be due to flex in the tool itself. Lead in will probably help as spunk has mentioned.
As to which is more accurate, that all depends, the servos/drives normally used on hobby type machines have low count encoders and can probably not be tuned so accurately and may actually be less accurate than steppers but better servos/drives with high count encoders can be much more accurate than a stepper. High count encoders will however require that you use electronic gearing in the servo drive when using the parallel port which may not give you any gains, the best option is to use an external motion controller such as the smoothstepper, dspmc, kflop, galil etc , you can then take full advantage of servos with high encoder counts.
Hood