The lack of AMEX and Discover seems irrelevant to me. The lack of local cards however is a major issue for some European countries, depending on what you sell. If I where to use Paymill, I would still need someone to handle payments on local Danish cards.

From the look of the API is also seems like Paymill wouldn't be of any use if you ship physical products. Some European countries don't allow you to charge the customers card until the goods are actually shipped. This mean that you do need to be able to reserve the money and later do a "capture".

I love the simplicity of solutions like Stripe and Paymill, but I really don't see them be all that useful. That might of cause be because I'm in the business of shipping physical products in small geographic location.

EDIT: Just noticed Dankort being supported by Spreedlycore, awesome.