One of the primary requirements from my customers in autobilling was that the processor post the results of the auto billing back to the originating site so you can update accounts in the database.
Don't disallow payPal, they have various API's and methods in place to do silent posts without leaving your web site. You just need to dig a little deeper. They also have the capability I'm about to describe (they call it IPN, Instant Payment Notification, but I am not sure how this works on automatic recurring billing.)
NetBilling has a recurring billing service that provides this functionality.
Authorize.net has recently caught on and is doing the same thing, although their ARB methods are significantly different than their purchase/payments methods. The normal purchases are done via post, but the ARB subscription methods are done via XML only. Funny thing is, when it posts the ARB results back to your site, it does so with a normal query string, not XML. It works though, I am finishing up a project for a customer using this API.
Basically you construct a script that "listens" for posts from the payment processor, parse out the results, and act accordingly (update or notify of a failure.) In A.N., you add your listener's URL to the Silent Post URL in the merchant account settings.
Generally a subscription/transaction ID is generated in the first request, this ID is stored in the processor and you must store this ID on your site. When the processor posts back, it will post back with a reference to this ID, which is your handle to determine which records to update.
In any of the above cases, an SSL cert is required and you must post and receive over SSL for it all to work.
Ease of installation I cannot say, it was pretty easy for me to set up but some programming experience is required. All of the above generally provide sample code to test with, and have test servers you can experiment on.