My experience with payment gateways (note: I have not tried the new subscription services: Chargify, Spreedly, etc) was that their recurring billing support was rather inflexible.

We had to implement it ourselves to get the customer experience we wanted (30 day free trials, that kind of stuff).

So this may be less of a downside than you suppose.

If you're looking at doing subscription stuff, check out spreedly, http://spreedly.com/. They'll handle all of the subscription and billing stuff for you, and abstract away whomever you end up using as a gateway. They do support Paypal as a backend.

I'm pretty sure Paypal does have recurring payments. I think they call it a subscription payment.

Perhaps you could combine it with something like Spreedly?

http://spreedly.com/info/payment-gateways/

I haven't used them before, but I am looking for an excuse to try them out.