I'm not sure how different Verizon is from Alltel when it comes to activating a phone from a different carrier but, this is what I just did.
I moved into a non Sprint area so I was able to cancel my Sprint contract. But, I had a brand new HTC Touch. So I then researched on how to unlock and reprogram the phone to use on another carrier. After I was able to retrieve the MSL number it was a cake walk
Anyway, once my phone was unlocked I went to Alltel and signed up for a new contract with a free phone. I then called tech support and said I just got a new phone off ebay and I wanted to activate it. The girl asked if it was an Alltel phone and of coarse I said yes
(I did have an official Alltel rom and prl on it though). She then told me we were going to program the phone manually. When we were done I had my Sprint Touch on Alltel with everything working flawlessly
I hope this helps ya