I'm looking for a payment gateway company so we can avoid tiresome PCI-DSS certification and its associated expenses. I'll get this out the way now, I don't want Paypal. It does what I want but it's really not a company I want to trust with any sort of money.
It needs to support the following flow:

User performs actions on our site, generating an amount that needs to be paid.
Our server contacts the gateway asynchronously (no hidden inputs) and tells it about the user, how much they need to pay. The gateway returns a URL and perhaps a tentative transaction ID.
Our server stores the transaction ID and redirects the user to the URL provided by the gateway.
The user fills out their payment details on the remote server.
When they have completed that, the gateway asynchronously contacts our server with the outcome, transaction id, etc and forwards them back to us (at a predestined URL).
We can show the user their order is complete/failed/etc. Fin.

If at all possible, UK or EU based and developer friendly.
We don't need any concept of a shopping basket as we have that all handled in our code already.
We have (or at least will have by launch) a proper merchant banking account - so cover services like Paypay aren't needed.
If their API covers Python (we're using Django) explicitly, all the better but I think I'm capable enough to decipher any other examples and transcode them into Python myself.
You might want to take a look at Adyen (www.adyen.com). They are European and provide a whole lot of features and a very friendly interface. They don't charge a monthly or set up fee and seem to be reasonably priced per transaction.
Their hosted payments page can be completely customised which was an amazing improvement for us.
Looking for a payment gateway