The 3GS firmware... 05.12
So after having my iPhone replaced I had great service yesterday. Early this morning I jailbroke it with Spirit and....still have great service!
I installed all my Cydia apps, put all my data back on, and have been running it all day without issue. Texting/phone calls, everything is working great!
So while I cannot deny that there was some issue with Spirit on the phone I had replaced I think that issue is gone now. Within minutes after jailbreaking the other phone with Spirit I lost service and was caught in an endless loop of Searching... and No Service. I don't know what boot rom that phone had, but it did have the latest OS 4.0 (beta 3) modem firmware on it because I had previously upgraded to the 4.0 beta. The new phone has modem firmware 3.12.01 on it.
Maybe that was the reason? OP, what modem firmware are you running on your phones that are having issues?