GPS best practice?

I'm experimenting with a ublox GPS module for a reverse geocache. Obviously the GPS module does not work inside most buildings. What would be a good approach to balance between these 3 requirements?

• user should be able to quickly obtain a position without a delay
  
• position should be more or less accurate (i.e. not too old cached data)
  
• power consumption should be minimized to allow for long battery lifetimes
  
  

The typical use-case would be that the user leaves the device lying around for days or weeks and then suddenly needs a position quickly.

We could run in deep sleep and periodically wake up to look for GPS signals, we could cache the last determined position, we should invalidate it (based on lifetime? moving speed during capture?, ...) but I'm not really sure which algorithm makes most sense.