PayPal's basic business account has subscription functionality. It does exactly what you described: you send a customer to PayPal, indicating what their billing cycle is and how much they should be charged. Once they payment goes through, paypal notifies you (via IPN callback) that the subscription should now be active. Once it expires (due to limits you have put in, or because the customer cancels, or if their payments fail), paypal pings you and you can update stuff on your side.
It's actually very easy to integrate, and provides a very good functionality set. It even has trial periods and such.
I imagine Amazon's payments system can do similar things.
Hmm ok, thanks for the info. I'll have to look into that.
Spreedly seems like a potential option as well.
WorldPay do this.
I don't want to re-implement a billing system, I just want to tell some API "This person should be paying X per month, let us know via some callback if they don't."
With all this sudden hyping of charging for web based software, you'd think there would be more choice out there.