First, let apend the statement above "...tell the processor that it is a recurring transaction ...so you get a discount on the transaction fees". The true cost of credit card processing is a percentage fee and a per item fee based on the type of card presented ( and some other factors I won't delve into here.) The point being, on a wholesale price plan, the price would be the same regardless of whether it was recurring or not because there are no special rates for 'recurring' in interchange. But I digress.
"Any advice on the best method / service / gateway for implementing recurring billing?"
Don't take on storing credit card data no matter what. You can't afford the liability.
The right choice depends on several factors.
As to credit card portability, has anyone gone to Wells Fargo/ First Data and gotten their data out? (Braintree ISO/MSP). I guarantee it won't be pretty no matter what so I would focus on the right long term solution, rather than the exit strategy, though it will certainly weigh in.
Here's questions that need to be answered:
How many transactions per month? For very low volume, maybe a few hundred, pick paypal pro. It's easy to get into/ out of.
Are people more likely to pay with consumer cards or business credit cards? Interchange optimization is important if business cards. (CenPOS automatically optimizes the transaction for lowest interchange qualification, paypal and authorize.net do not)
What methods does my client accept payments? self pay on internet only? Phone orders? Mobile payments (special events or retail)? Choose a gateway that fits all their needs.
Do you need to charge on specific days- ie the 1st and 15th? Or any time? If on specific days, how will you prorate? Check the answer against the gateway flexibility.
What happens when a card expires?
What happens when a transaction is declined?
Who will need to see the payment data for customer service? How will they access it?
Determine your needs, then figure out which ones meet them.
For the record, CenPOS is the most robust solution, but may require more steps to integrate since they are newer to ecommerce.
Disclaimer: I've been a business user of paypal and authorize.net for probably a decade and more recently CenPOS. I'm also an authorize.net reseller, and CenPOS direct agent.