Unhappy [Q] Thought all Verizon 4G phones were carrier unlocked.

Greetings.

It seems I'm facing a weird problem here.
To begin with, I live in Europe and I've just bought a Verizon M8.
After boot, a pop up reads that this sim card is not from Verizon.
Although, my sim card CAN receive calls and messages (there is also the app from my carrier services) I cannot make any calls.
What happens is that when I'm trying to dial a number, +1 appears in front of the phone number and call is dropped.
+1 is the phone code for the US.
Well, I don't want this.
I thought every single Verizon 4G phone was carrier unlocked out-of-the-box.
To be honest, I know it, because there is some kind of legislation forcing Verizon to sell their 4G phones unlocked.

Could anyone please help me?
What should I do?
Flash another firmware? And which one?
Nexus 10 4.4.4
HTC One M8 Gunmetal grey + HTC One M7 Red Edition (ViperOne on both).
...and iPhone 3GS ...for breaking nuts.