Fasty Error in New Environment

How long after the creation of a new environment should I expect Fastly unknown domain errors like:

Fastly error: unknown domain: blerg-staging.moovweb-edge.io. Please check that this domain has been added to a service.

Details: cache-ewr18149-EWR

We do our best to check that the domain has propagated properly to at least your nearest edge POP before marking the deployment as successful. So this message is rare, but does occasionally show up, especially if you are near more than one edge POP. It should go away after a few minutes and should only happen after the first deploy of a new site.