I feel that the agent starts up before the network is fully initialized (since this happens predominantly on our faster SSD based systems).
It tries to contact the internal server at startup, fails because the network isn't fully initialized, then attempts to contact the PDQ hosted server, at which time the network has had time to initialize.
An easy fix could be to add a couple of seconds for a second "internal' attempt, and only then to look for the PDQ hosted server, or maybe set the PDQ agent service to "Delayed Start".
Alternatively you could have your network admins block outgoing access to agentsapi.pdq.com on your perimiter firewall so there is no way for internal machines to ever be "external"; but such a 'fix' should not be necessary. When I'm really in a hurry and I know the machine is somewhere in the network I force a rescan or reinstall the agent.