@freakshow...I wish I knew more to comment about what towers ST uses, but I briefly searched for your device...:
Samsung Galaxy S III SCH-S960L LTE (Net 10 and Straight Talk) Specifications | Smartphone Zero
General & Network
2G: CDMA
3G: EVDO Rev. A/PCS 1900 MHz
4G: LTE B25
Also, from what I've found, Verizon and ST parted ways, which would appear to me, like you have stated, your phone runs on Sprint towers.
Now, I would assume your Sprint signal is poor and connects to Verizon's towers...or attempts to.
I don't know how you can force your device to run on Sprint only short of what funky said and turn off roaming?
Some findings of mine....the box that the device came in..on the front/lower corner...does it say CDMA-V, or CDMA-S. (V=Verizon, S=Sprint)? I'm curious.
Like I said, I wish I knew more about your issue to help.
How long ago did you get this device?
Perhaps instead of messing with the APN settings etc, it may be easier to just call your carrier like you said you may do, and see what they can offer?