When you start the vehicle is it in a garage or under a carport?
There is no delay for the message. The message is being set because the GPS is not locking immediately or there is an issue with the present map installation.
This is a 2011 Explorer?
Obviously a Sync 3 retrofit. Was the vehicle originally equipped with Sync 2?
Has this issue been persistent since Oct 2021?
What is the year or part number of he replacement Sync 3 APIM?
By the way… There are new NAV-Voice files. See the tutorial: Tutorial: Current EU Maps Installation on US Imported Vehicles - Ford / Guides & Info - CyanLabs Official Community