There's another workaround for this here in England is to go to a market in most towns, look for a man in a turban and chances are, he's running a mobile phone stall and will unlock anything.
Not much use to you if you have no such trading where you live but it might be worth asking around. I'm not surprised at Verizon's behaviour; it's typical of big business these days.