They use the same network technology- GSM, not the same network infrastructure.
Um, wrong. I used to work for Cingular and helped with the GSM roll-out and setup. I am pretty well versed and believe me, I know what I am talking about!
The VAST majority of GSM networks are shared between many carriers. We hear of T-Mobile and ATT (Cingular) but there are many other smaller ones like Cell One. Anyway, most of the GSM network is owned by Alltel. Oddly they do not sell GSM to their own subscribers. But Alltel does own the bulk of GSM networks in the US, especially in the central areas, less so on the west coast.
As part of the call codes setup, any part of the network can have a carrier code assigned. If the carrier thinks its a good idea to have service in an area, they pay for that tower signal lease and they lease the same towers to anyone they want for a flat rate. If a carrier does not have customers in an area and feel no demand to provide "access" they pay for the usual roaming package where Alltel bills (a premium) to the carrier per minute or connect and the carrier absorbs or passes the buck onto the customer.
So sometimes is cheaper in an area to not be under tower lease contract. Or in metro areas, its cheaper to setup contract.
It almost comes down to simple coding and a signing of a contract for a carrier to expand the network now days.
By nature your phone want to avoid an "off network" call code so it latches onto contract towers as often as it can. This can cause random signal dips and peaks on the fringes of "contract" towers and non-contract tower. The signal is even, but the phone wants the contract towers.
You can add the off network code to you phone. Instead of just showing ATT all the time (or in the case of the iPhone, any carrier hacked logo you make) it will show "Off Network...".
Think of Alltel as the old WorldCom or Ameritech where they provide the backbone but carriers such as Road Runner and you local dial-up ISPs use it. Its no different and very common, always has been.