We are using Authorize.net's recurring billing service, and we are very happy with it. Mostly because we don't need to worry about the security issues you mentioned (encrypting, secondary processing server, etc...). Authorize.net stores the c/c info and takes care of it.

Paypal also does that, but we chose Authorize.net mainly because Paypal is not completely behind-the-scenes in the process (I don't remember exactly, but I think PayPal forces you to redirect the user to a PayPal page). Also, Authorize.net is cheaper in the long-run.

The downside of Authorize.net is the account set-up, which is a bit cumbersome. A provider will contact you and you need to describe them how you are going to use the account, etc... Also, I think you need to open a merchant account. It's not painful per se, but you should expect at least a week to get the whole thing up-and-running.

On the upside, Authorize.net gives you access to their test environment in the meantime, so you can do the integration while you wait for your account...