We love Stripe, Samurai, Braintree and services like that. Unfortunately, they're not available for companies outside of the US.
Most people say that we need to use Paypal. But we prefer to work with Stripe for example, because it really looks like a great service and a service with a refreshing way of working with payments.
Does anyone know or have experience with using a recurring service that is accessible for European companies?
I would suggest looking at Recurly as your integration endpoint for a few reasons:
1) Multi-currency. Some people claim it's "expensive" as as $200/mo add-on, but the extra conversions from geo-targetting visitors with their native currency make this a no-brainer, especially for UK companies.
2) Data portability. You can leave Recurly in 5 years if you want to write your own recurring billing app or switch to somewhere else and they will give you your data.
3) Not having your customer's CC details held at the gateway (Recurly are best described as a value-add intermediary) means you should be able to easily switch out gateways later on. This is a key architectural choice that I don't think people pay enough attention to, and Recurly really don't promote it enough. Chargify etc do not do this, instead they store your customer's details at the gateway and have no power to retrieve them ever again.
4) Supports VAT.
The down side to Recurly is their API is a bit messy. Their hosted payment pages and "transparent API" appear to be next to useless if you want to also record extra information (e.g, username) as part of the signup process in a seemless way.
With regards to payment gateway, pick any payment gateway from here: http://recurly.com/features/payment-gateway-support
The truth is, it really doesn't matter. As long as it is working, and your bank/merchant account doesn't put a hold or delay on your income.
Don't stress about the transaction fees. People get too hung up on a percentage point, with the frame of reference that "when we've got $10m in revenue, that 1% is worth $100,000)", but honestly, when you get to that point, you will have enough business savvy to re-negotiate or look for a better deal then. When you don't have any customers, it really doesn't matter.