The company had actually already chosen Samport, a provider mainly (only?) active on the Scandinavian market. However, Samport fulfills all requirements that I previously described.

Actually, if there are any Scandinavian developers/entrepreneurs reading this - give Samport a chance. In addition to the previously described advantages, they are also cheap and -- besides the hosted solution where customers are redirected to their servers -- allow you to seamlessly integrate Samport with your own e-commerce.

Regards, WarTheatre