[full disclosure - I am a co-founder of Recurly] I'll do my best to be objective and help frame an inclusive approach to the answer.

First - you need to decide what kind of billing mechanics your business needs. (simple X$/mo or advanced- multiple plans, upgrades downgrades, add-ons, coupons, dunning, multi-currency support etc) - this is typically the first step in the build vs. buy eval.

Secondly - you need to evaluate your own available time/resources. Most eng. projects require 2x original estimate...you can easily apply 5-10X for billing since even the most talented developers don't get it 'right' the first time (add PCI and ongoing customer support + gateway recourse to your total estimates). The best developers can usually 'get it working' - but then realize they end up spending tremendous time to 'get it working well'.

Third - [Assume now you're buying vs. building] You need to choose a service that gives your business room/flexibility to grow. Many businesses decide to change gateways at some point - when new business needs emerge - [multi-currency support, better rates, customer support]. Don't hem yourself in by choosing a service that doesn't store your card data, and let you easily switch gateways. Numerous horror stories exist on this topic - won't cover here. Also important, don't choose ANY service that won't commit to returning your customer credit card data if/when you decide to leave them. [Braintree was a leader in this area, and Recurly fully supports the Data Portability Standard as well].

Compare core feature capabilities AND 'high frequency use' capabilities of available recurring providers. Core features might be: add-on support, upgrade downgrade + proration, customizable emails, API documentation + API behaviors, Push notifications for sync to your systems, free trials, coupons etc.
'High frequency use' aspects include reporting, data exports, third party integrations, account dashboard + common customer support functions (can you easily credit, refund, charge, modify info, upgrade/downgrade) from any customer account page. This is a critical aspect and most evaluations fail to consider what it will be like to actually 'live with' a vendor's solution.

Lastly, the payment processor options + combinations.
Merchant Bank Accts - (We really like FeeFighters.com for helping entrepreneurs to choose a merchant bank).

Payment Gateways - Your payment gateway decision should be made not just on fees alone, but also consider the kinds of error fidelity you will receive (How many error/decline messages and what type of info is returned). Another important consideration is multi-currency support. Does your business need to accept many different kinds of currencies from around the world? (Dramatically improves conversions if you don't force your customers to pay in $USD). PayPal does a better job with currency conversion than just about any other gateway (For US companies). Some gateways will require you to be incorporated in each country you would like to accept currencies from..

Most importantly, talk to customers from your prospective recurring billing provider. The 'Net promoter score' opinions are very palpable across vendors. Don't just take the 'reference' customers provided by the vendors, but do your homework and you'll find quickly where the raving fans are.

Hopefully this was helpful, balanced, fair and objective.

-Dan