Actually... since these guys are YC - I offer my .02Cents.
There are a number of us in this exact situation and it is a GIANT pain point. This market is basically untapped... if you can/want to tackle non-US payment processing, you will make a killing.
I do consulting work for a friend who has a surprisingly common problem:
He needs to do card processing but only certain times out of the year. He goes to conventions and sells merchandise, etc and wants to be able to take credit cards but the monthly & inactivity fees would wipe him out.
So far all I've seen that could fix this potentially is Square, but they have yet to ship out their swiping widgets to use to try it out.
If someone can find a way to make it affordable to process cards "When you need it" it might be huge.
Pretty strict, normally all merchant account agreements mention that you can't process cards for anyone else or any other business/purpose/website other than the one listed. They like to keep a tight eye on that.
You can of course deal directly with credit card companies like Visa and Mastercard - they have well documented APIs for interfacing with them directly.
Back in the late 90s, RedHat bought a small company in Pittsburgh which made a rather awesome product called CCVS (http://en.wikipedia.org/wiki/CCVS) which allowed you to talk directly to the credit card companies, circumventing the merchant accounts.
My employer started using CCVS to provide direct credit card services at the time, and I wrote a PHP module which shipped for a few years as part of PHP core for using it.
Sadly, RedHat discontinued the product ; I'm not sure if anyone else has stepped up to do something similar but it was incredibly easy to use, powerful and got around the absurd restrictions most merchant accounts provide.
I'm assuming Square is talking directly to the CC clearing houses, which is how they keep their costs reasonable.
You are right on the money (pun intended). Europe and Asia are two huge markets with no fast and easy solution to payment processing. There's about a handful of providers who are 'so-so'.
We ended up going with Paylane (merchant account setup took about a month - which is insane). Worldpay was another option but they required people who wanted to pay for our service to have an account on theirs (seriously).
There are a number of us in this exact situation and it is a GIANT pain point. This market is basically untapped... if you can/want to tackle non-US payment processing, you will make a killing.