I hear what you're saying, but the 100K other phone comment seems a bit of an embellishment to me
Cell towers don't usually connect hundreds of thousands of people do they?
Packets are lost, and have to be retransmitted, but I often get 250k-512k of bandwidth with 200ms as the average ping. That should run VoIP just fine. How many packets do we drop on average currently with data-only 3G? I'll also point out that most of the things you mentioned that would interfere with an IP voice packet's transmission would affect a voice call as well (can you hear me now?). Choppy audio is better than NO AUDIO.
Cram voice packets into the 3G data stream, and tag the hell out of it. Then you can offer voice and data at the same time. Software/Firmware updates only, no hardware changes should need to be made.
Is the solution to add two EVDO radios to the phones? One to send voice and one for data? Each user (if they happen to receive a call) would need to take up two resources from the tower. I'm not saying it's mandatory for them to take up the resources...only if they are actively using data and on the phone. Eventually, this will use up space as more clients try to connect to the same towers.