Jeremy,
Have you tried applying directly to your bank for a merchant account? My company found it much more efficient and less restricting than an online service.
At first when we started out we used ibill (http://www.ibill.com) but after a while came to the conclusion that they were not competant enough to manage accurate and consistent rebilling of cards so we decided to ditch them and applied to our bank for an IMA (Internet Merchant Account). You may have to put down a deposit because you have a net business (it was only about $1200 for us) but it should be worth it in the long run.
If you expect to get thousands of customers then it is a good idea to use it in association with some quick-to-administrate billing software that supports recurring payments.