Lynxsky: I like the equipment in the link, and would love a setup like that. Further thoughts for your consideration.
If space/portability isn't an issue, i would tend to go with the bigger motor; not only does it take away the 'will/it won't it worry, but if you can wear the increase costs of power supplies etc, then the motors are better driven well within their working envelope, than on the ragged edges and run the risk of a missed step.
Also, further to a point made earlier in the thread, these motors will get warm if in use at full power to periods of time. An over sized motor would allow you to run them at lower power, but it still has a greater thermal mass to help reduce the effect of any temperature issues.
I would tend to stay-off motor gearing if possible, since using them will increase the backlash of the system. Motors direct onto the worm drives are probably best.
Also, although the majority of stepper motors are 1.8degs step, that are others. On ebay you can source 0.9degs for similar prices. This will double your resolution without degrading backlash.
Final thoughts on motor drivers: Using micro stepping will improve your resolution, but it is associated with a few issues:
1. The stepper motors are designed to step forward one complete step (say 1.8 degs). Using microstepping progressively energises the coils in graduated sequence to 'fight one another' to hold the angle of movement between the designed steps that motor has. As soon as you de-energise the motor, the motor will snap back to a 1.8deg integral angle.
2. you loose torque using micro stepping - so re-enforces the case for over-sizing.
3. Obvious really, but gives a much smoother angular rotation with less stepper vibrations, which (unless using a geared system) might be material issue in the system you design.
4. Higher the micro-steps means your microprocessor needs to work harder. I played around with Raspberry Pi systems, with driver code written in Python (being interpreted) will struggle to operate high slewing rates - i've tried 128 microsteps, and rotational limits were imposed by software (900MHz processors!). Ardinuo systems (8MHz) quite evidently would struggle. So: use multi-core-RPi-3 (not Zeros) and consider compiling your code!