Ublox Neo-6M
I have used 4 of these and just received a "7" but have not tested.
Warm start in under 30 seconds, typically 10-15 seconds.
The 6M are available for under $17 delivered, I love 'em but I am only using the RMC$ sentences and I hacked Ladyada's lib lots!
http://www.ebay.com/itm/181293242043
Ray
http://www.hackster.io/rayburne/5-billion-arduino-gps-clock-for-25