So have found the answer, I think. Mentioned earlier in the forums, but now somewhat obscured. You need to connect your Edge to Garmin Express on your PC. That will transfer a file named EPO.BIN to the Edge that helps the unit find the satellites. Syncing via a mobile phone doesn't do this. The data in the file do get old, that's why the delay gets longer and longer and why you'll need to connect directly to a PC on a regular basis to refresh the file. For me the difference went from 15 mins+ to less than 1 minute.