Which payment provider should I use for recurring payments/subscriptions as a European business?

We're building a web app that customers can pay a monthly rate for. Here are the requirements:

• We want to charge customers monthly fees to access the service
• We have several different plans
• Each plan comes with a month free trial
• Upgrading/downgrading should be straightforward
• We want to support as many payment options as possible. Our software is aimed at freelancers and small businesses so we want to support credit cards, PayPal, and European payment services like ideal (debit). Google Checkout and Amazon FPS would be great too.
• The quality of the user experience during checkout is important: SSL, co-branding, and clarity in the UI and copy is a must

I've looked around at various options and concluded the following:

• PayPal's UX is pretty poor, they're prone to whimsically changing their checkout process, documentation on x.com is outdated and poorly maintained, and they require some unacceptable adaptations to our app in the form of default payment options and buttons
• Google Checkout is only available for US and UK based businesses
• Amazon FPS is only available for US based businesses
• ClickAndBuy only has 13 million users
• Dutch services like twyp and ogone have good support but outdated APIs/service architectures

My question, then, is: which payment provider should I use, given that I'm a Dutch business and therefore am limited in my options? What are your experiences and what would you recommend?

I wrote a blog post describing some background of my specific situation if you want more info: http://blog.quplo.com/2010/08/adventures-in-integrating-payment-services-as-a-dutch-business/

We ended up choosing Spreedly for subscriptions and Ogone/Atos Worldline for the gateway and merchant account. I wrote another blog post describing the situation: http://blog.quplo.com/2011/01/looking-back-on-the-quest-for-payments/