If you're generating addresses with proper entropy, the sun will burn out before the chance of a collision is greater than winning the MegaMillions lottery 3 times in a row (approximately).  In other words, it's a waste of time to worry about it.

However, as I reread your original post, gmaxwell may have misread your question and thought you were asking about collisions.  It doesn't look like you were, so that may be an irrelevant response (unless you modified your post since then).

bitcoind is the base Bitcoin engine.  Bitcoin-Qt is simply bitcoind with a graphical user interface.  For the purposes of building a webservice, they are nearly identical in functionality, though you'll want to use bitcoind since your web service doesn't require a GUI.