I have been using Namebay since the INFO landrush, that is some 8 years ago, for a number of my domain names, especially names that I want to be safe. I moved a number of domain names since, but still have some 30 with them, including one that I consider to be probably the best in my portfolio.
And I must say I have never had a bad experience. Not the cheapest rates, but reasonable. Interface could be better, but is acceptable. And security seems to be good. Never any major problem with them. And when you call them, there is a real person on the line (at least those very few times when I needed to do it).
However, since you mentioned it should be also outside the EU: they are obviously in Monaco, but I do not know how far a number of EU rules also apply in that small principalty, due to its close links with France. It depends what your concern is, of course.
---------- Post added at 08:47 PM ---------- Previous post was at 08:42 PM ----------
Regarding Rebel.com: nothing exceptional, but definitely a reliable registrar, support answers questions. I have however only some 10 domain names left with them, because I do not like the fact that they do not send a courtesy email when a domain name is transfered out, as it is done by many registrars. I asked them the question last year, and here is the reply I received from support (as you see a personal reply, which is a positive sign):
Rebel.com does not send out courtesy emails when domains are transferred for various reasons. The fist and foremost is because it is not required by ICANN. In order to transfer a domain from REBEL to another registrar there are steps that would have to be completed by someone, typically the account holder and domain owner, these steps include requesting the authorization code and most often it requires that the domain has registrar lock removed.
They are right, of course, still I feel that a courtesy email would provide an additional layer of security, and there are never enough such layers when it comes to domain names.
With Namebay, you get a security message each time a change is made to a domain name (e.g. changing DNS, etc.)