I'm setting up a similar service using
AlertPay instead of PayPal. It's quite simple, actually... your client signs for a subscription through AlterPay/PayPal and their server pings back to your server every time a (scheduled) payment is made. You just need to implement a script that processes those ping backs and handle the client administration on your end.
AlertPay requires that either the client or the merchant log into their server to cancel a subscription, but otherwise their system is pretty much what you want.
(If you'd rather go with PayPal, I think their service is similar, although in my experience a bigger pain to implement, which is why I switched)
PM me if you need more details.