Looking for a payment gateway
I just finished something exactly like this using First Data Global Gateway (don't really want to provide a link, can find with Google).  There's no Python API because their interface is nothing but http POST.
You have the choice of gathering credit card info yourself before posting the form to their server, as long as the connection is SSL and the referring URL is known to them (meaning it's your form but you can't store or process the data first).
In the FDGG gateway "terminal interface" you configure your URL endpoints for authorization accepted/failed and it will POST transaction information.
I can't say it was fun and their "test" mode was buggy but it works.  Sorry, don't know if it's available in UK/EU but it's misnamed if it isn't :)
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.