There are three categories of causes:
Blocked signals: slot canyons, trees, buildings, large metal objects, heavy rain, and even your own body can block, weaken, or confuse the signals. Although the constellation of orbits means that the satellites can appear everywhere in the sky, at even given time, the satellites might be somewhat bunched in one part of the sky. If your body, a tree, or a cliff happen to be between the camera and the satellites, you might not get a reading.
Interference: Other nearby devices such as cellphones can jam GPS signals.
Time-To-Start: The GPS signals are recurring patterns of codes and data. If GPS has been off, it can take time for the receiver to gather that needed data, including waiting for the satellite to transmit data on the satellite's location. The result is that it can take the better part of a minute to get a lock (
Time to first fix - Wikipedia). If you flick the camera on, quickly compose and fire, the camera may not have had time to get a GPS lock. (I seriously doubt the camera adds the GPS data to an already stored shot if the GPS lock doesn't happen before you hit the shutter button.)
Solutions:
1. Wait for the GPS light before shooting. (Yes, I know that may not be possible when hiking on a schedule or shooting wild critters.)
2. Turn on "GPS Time Sync" (One of the delays in getting a lock is if the camera's clock is off by more than 20 seconds.)
3. You might try turning GPS logging on at the beginning of a hike. That should increase the chance that the camera has all the needed satellite data when you want to take a shot and likely reduce the time-to-subsequent fix to a few seconds. (At the very least, GPS logging will also provide a track of your hike that you could use in conjunction with the time stamp in the EXIF to identify where you took the shot.)
Good luck and have fun out there!