Pidgeot: According to the error message, they use an online service to verify that you really are who you claim to be, but that service only appears to cover the UK. Ireland might also be included, but the rest of Europe surely isn't.
Vitek: Hm, tried changing my location to UK but had no luck. Still the same message. :-(
Well, no, because it verifies your *identity* using that service. Presumably, *all* of the details would have to match someone in the UK, including the name and specific address.
They really should have skipped the identity check for customers from other countries, or, if that wasn't possible for some obscure reason, simply not allowed registrations from countries not supported by that service.