I settled on OpenProvider.com (Netherlands). If you have lots of domains you can get reseller access and buy domains at no markup, basically.
The only annoying thing is that you need to add money to the account instead of simply paying for the domains.
The “I know a little german” joke kills me every time :D