Those funny VZW guys
A (really important) point lost on non-US readers is that Verizon's network is CDMA/EDVO, not GSM. Cool phones from South Korea might be possible, but to get an iPhone or just about any Nokia onto the VZW newwork would take a bit more work. With a soldering iron. Good luck with that.
Verizon's phones are all sold unlocked (contract or not), and Verizon will already activate anything that can talk to thier network that has a valid, known ESN. Of course nothing but a VZW phone can actually talk to their network, and the phones are completely useless on other networks.
It's really funny to see how much mileage Verizon is getting out of the media on this though. The Euro press, used to a mature and functional wireless market, see this as something new and exciting - look at those cheeky bastards getting the drop on Google! While the US press - mouth-breathing morons for the most part - regurgitate the press release. Mention that 'open network' + 'no frickin hardware' = no change and their eyes glaze over.
The bit in the original press release about 'testing and certificaiton' is the real gotcha though. Take a look at Verizon customer forums to get an idea about how long that takes. I think they are still waiting for their first WM6 device.