I'm using different modem but I have the same problem.
I'm using Gps Data to show satellites. At first it shows around 20 satellites after that the amount starts to drop to 9-11 satellites.
It can always get one fix for a moment to some satellite (usually 71, 72 what I have been following today) strength is 40-41 but it loses it in 5-10 seconds. At the same time it also always shows strength 30 to three other satellites.
After it has that one fix and 3 others with signal no fix it drops them all and looks for new ones and does the same thing after a while: one fix again to 7X number and 3 signals no fix.
Interestingly enough the one fix it gets seems to be russian satellite and the 3 others are american... still, I don't think that's the problem or could it be?
Before I had problems with gps and 3g too (only got 2g) so I sent the phone to repairs. Now 3g works and the gps signal strength got to that 30-40 to at least some satellites. Before warranty repair it was around 2-4 satellites and signal was only 3-10 and never fix.
They told me they had changed the motherboard of the phone other than that I don't know what was the problem since they spoke only Chinese. I'm in Shanghai btw... so 3g got fixed but gps still no lock.
After repair I have tried 3 different modems and unrooted stocks. Same problem with all modems and firmwares, same satellites, same strengths.
My friends Sgs 3 and Sgs 4 have no problems. I also didn't have any problem at the first.
Did you get your phone fixed somehow or was there HW repair ?