I think most difficult problem is still proper accounting. I'm with a client right now, based in Europe and we had >really good time< integrating Recurly with Stripe and use it as their payment provider, but we got stuck when we figured out that there was a need to hire an accountant to handle the cancelations for us.
Having a service like Cleverbridge [1] / Avangate [2], where they end-up having someone to manage this for them for a bigger % of the sale, was the better deal.
Not sure how the startup-scene will solve this, but it's actually still really hard to do this properly.
My best solution would be to have Stripe doing whole-sale solution, where they invoice customers and you simply invoice them each month.
It just takes too much efforts to do this >legally< in Europe if you are on your own.