I started having this problem in December 2012 and I have spent countless hours looking for a fix including but not limited to:
phone resets, clearing cache, battery pulls, changing the settings in Location services, uninstalling maps, reinstalling maps, rooting, custom ROMS, removing my case, running GPStoolbox, FasterFix, FasterGPS, and numerous other apps. There is even a "fix" saying remove the back and tighten all the little phillips head screws.
Here's what I know.....this Searching for gps problem has been reported on all types of android phones, Nexus and non Nexus, on all versions of ICS and Jellybean, on new out of the box phones and phones where one day the gps works and the next day it does not, it has nothing to do with downloading a new app, it happens on rooted and non-rooted, custom ROMS, stock ROMS, on Verizon, ATT, T-Mobile, Sprint...and most importantly Google knows about it this problem. June 2012 Daniel M. Community Manager, Google Maps started a Google thread under Google maps asking for input on this very problem. Unfortunately the thread is now 21 pages deep with people reporting the problem. There are at least 10 other threads in Google forums with people asking about this problem as well. Daniel M has remained completely silent on this issue since he first asked for input.
Google Groups
I've tried every "fix" I could find in XDA and my SG3 just got a map update on May 15, 2013 and I still have the Searching for GPS problem.