In this case adding the port number to the license server name 27004@myLicenseServer appeared to fix the issue. We had tried the FLEXLM_TIMOUT=5000000 (5 seconds) but that appeared to have no impact on this issue since the 'you are not licensed' window would pop up immediately after starting ArcMap (no 5 second delay was seen).
I also found that the registry setting for in [HKCM\SOFTWARE\WOW6432Node\ESRI\License10.5] for the "DESKTOP_CONFIG" key was set to "FALSE". I changed this to TRUE to match my other working installations. How this became FALSE is unknown.
Note - the office location with the problem was using a VPN as well.
Thanks for the ideas :-).
Rich