To get some closure on this topic: Starting up gpsjinni before opening Maps helps get a lock even without an Internet connection. I guess the Maps developers should beg/borrow/steal the code from gpszinni.