question

In my experience this will be a network configuration issue or a loose handset cable/bad phone.  You should be able to rule out the phone pretty quick by trying speaker and handset and checking the handset cord.  Assuming it may be firewall related, what model firewall do you use and do you manage it?

We are using MicroTik routers, and are on an MPLS managed fiber WAN network. I've sent the network requirements to the folks that manage the routers for us so they can make the appropriate changes to help the issue. Hopefully that will help out. We had already tried a different handset and using speakerphone mode.