ICE fails with server behind NAT, ONLY for some internal clients!

The server is in a private network behind NAT. By setting the publicIP for both erizoController and erizoAgent in the Licode config, external users are able to connect to the server and publish/subscribe.

The problem is with some internal clients which are able to connect but can not publish/subscribe and get ICE failed while some other internal clients (with exactly the same OS/browser/config and in the same network) can! OTOH when I remove the publicIP then all internal clients are fine.

What would be the reason? I know using a TURN server may fix the problem but I’m curious to know why this is happening. How can I trace the issue? Any help would be appreciated.