Well, it looks like GPS is really wonky on my wife's S3 as well. She is running stock rooted AT&T ROM. At random times while driving with GPS on GPS would just stop working, no icon showing at all, GPS Status doesn't show any sats. The only cure is to reboot the phone. Toggling GPS on/off doesn't help. I did full wipe reinstall before and the problem persists.
It feels like software problem. The weird thing is that init.rc on the phone does reference some gps daemon that doesn't exists in /system/bin and I suspect that all the GPS data is coming from RIL and modem firmware. But I don't see anything suspicious in logcat.
I followed all the steps in the OP, and flashed the gps zip as well, now it gives me "location set by GPS" in the notifications, but when I go into Maps, it says it's "accurate to 1000 meters"... I've had GPS working correctly on this phone previously...
running CM 10.1 nightlies, i know GPS was working as of a couple weeks ago, but hadn't really checked recently until today.