This is very possible I am living proof. I switch from Sprint to Alltel recently without a hitch.
The first thing I did was research switching a sprint phone to a different carrier. Everything I found said it couldnt be done. But I was determined
So the first thing I did was unlock my phone by getting the MSL number (using GETSPD) and reprogramming it to 000000 (using QPST). Then I flashed to the official Alltel rom.
So now my phone was unlocked and ready to go all I needed to do was get service with another company.
I then went to an Alltel store and signed up for new service. I just got the free phone for now till I could get my Touch hooked up.
I waited about a week and called Alltel Tech Support and told the girl I needed to activate my new cell phone I got off ebay.
The girl asked if it was an Alltel phone and I told her yes it says Alltel when I turn it on

Then she asked for the ESN number which I gave her. She then said we will have to manually program it. At this point I just followed all her directions. After we were done I had a working Sprint HTC Touch on my new Alltel account.
So this is possible with the right amount of research and effort.