Hello,
3CX Support will not be able to help you and they were correct to point out that you need to check your firewall.
2 of them have a firewall and the other one doesn't
They all do, the firewall is in the ISP modem, or in the ISP core network. Customers always need some kind of routing / NAT device to bridge them on to the internet, and that will usually act as a firewall. And on some less common connections, the firewall is in the ISP datacenter.
We didn't make any changes on 3cx nor the firewall
It's very typical to hear this in STUN cases, one day it just decides to stop working. Search the forum and you will find many similar cases specifically for STUN. You can also read the solutions there if you want to give it a shot.
I know that every phone needs to have a different Local SIP port but it not working anymore
Some times this is not enough. The hardware that connects you to the internet might do something you are unaware of or there may be a small misconfiguration somewhere that wasn't affecting you until finally it did.
There are two solutions that will make this go away:
a) use a 3CX SBC with your IP phones, it was designed exactly for cases like yours and will very likely solve the issue permanently
https://www.3cx.com/docs/3cx-tunnel-session-border-controller/
b) or remove the IP phones at those locations, and use the 3CX apps which are not easily affected by the ISP or modem or firewall combination and their side-effects.
If you have the time, knowledge and effort for running multiple packet captures on 3CX, on your firewall and on the individual phones, and then comparing them in Wireshark to find where the needle in the haystack is, you could probably find exactly what it is that breaks the connection (3CX Support will not do that for you - we don't troubleshoot your firewall). And even then, you might discover that it's something you cannot change due to a provider limitation (ie. they decided to block SIP or certain ports) or a hardware limitation (SIP-ALG is active on the ISP and cannot be turned off).
On the other hand if you value your time, then seriously consider using the apps or the SBC which were made to bypass these issues.