Are they using the same exact link, or just links to the same form?
My first guess would be that they have two separate instances/URLs; One accessible from the Internet for the public, and one hosted within their network for internal users.
The public instance would have the Public Portal license, but the internal site probably doesn't.
As a result, Anonymous access would only work when using the external URL.
If that is indeed how their environment is configured and the employees are using a URL for the internal site, that would explain the login prompt.
The easiest way to check would be to go into the Access Rights for any of the forms using both the two different URLs.
If you see the Public/Restricted options, that instance has a Public Portal license.
If you don't see the option, that instance has no public license and doesn't allow anonymous.