I'm sure I'm now the only one who have always had problems when choosing or working with payment processing service. There's always a problem with them - bugs, ridiculous policies, too high rates, etc. So I thought it might be good to share some of my experience.
PayPal appears to be the most popular and although it had its issues some years ago, now I think it's probably the best choice. Frankly this is the one I recommend to all my clients. Easy to integrate, support various payment options, low rates. A major downside is the inability to test with your account, you need to go with their sandbox. Don't get me wrong - PayPal isn't brilliant at all, but it's "least bad" of all I've worked with.
2checkout is also good, although their admin interface is hard to work with and has some bugs. Their rates are higher than PayPal's, but still bearable. I use them for 8 years and I can say they're good. Beware though - they don't allow dating sites, and there are many other restrictions as well - make sure you read their policy for allowed sites.
Authorize.net is also fine, although I'm not sure if they supported the recurring billing - but I guess they do, it's a must for many sites today.
I'm not what was the case with Worldpay's fees, but I've noticed there's too much bureaucracy with them - they have too many rules to comply with. But in general they're fine too.
We've also worked a lot with the British provider SagePay (former Protx). It takes some time to learn how they work, but once you do it, they're fine. And I think their rates are good too.
I've worked with other providers too, but there are always issues with them. Not that I hadn't had any with the above, but still, when a client is to choose a payment processor, I always recommend ones we've worked with, rather than ones we've never heard of.
When you choose a provider, make sure they have a good support! There ALWAYS ARE technical issues, well, unless you're having a very simple payment - i.e. no recurring, no payment notification. So there must be someone to answer your questions.
Oh, I forgot one of the most popular ones, and my greatest disappointment - Google Checkout. Google always do things right - their search engine is brilliant, their maps revolutionized Internet, the translator does an excellent job, so I thought their payment service would be good as well. It wasn't. It's the one of the most difficult processors we've ever worked with. So I'd stay away from Google Checkout, until they improve it.
And finally - be very careful if your site has adult content! Finding one is truly a mission impossible! The good ones are quite high (10% or higher commission), and almost all of the above (if not all) disallow adult sites. And which is worse - sometimes they let you use their service for a while and then they suddenly say you violate their terms and block your account. I'm not sure what happens to the money you've collected but the block itself is a pain if you have members paying and you can't take their money until you integrate a new payment service. I guess it's not their fault - simply they have no time to review all new sites at once, they do it over time, and the moment they find something wrong, ban you.
Some of them doesn't make it quite obvious they don't accept adult sites, so please make sure that you read every piece of their policies, and to be on the safe site - ask them directly.
There are other things to observe when choosing a payment gateway - such as how often they pay you, what currency they accept, etc.. Also there are other populars I haven't mentioned here - such as Moneybookers (I checked them some time ago but I gave up for some reason, I don't remember why). So the above is NOT a review or anything - it's just sharing my personal experience with these services.
I hope this has helped, and I'll appreciate any corrections or additions to the above, as well as your own experience.