The solution I'm proposing locally for our ham club battling CGNAT and Private IP's (and digital radio) is to use OpenVPN (Layer 2 TAP) and obtain public IP's from the 44net. That would only be for Amateur Radio use though (Allstar, Echolink, etc ...).
For your Cisco SIP phone, plenty of routers support VPN services and would set it up as your default gateway. More advanced methods would allow you to tunnel VPN traffic for only SIP. However, there may be increased latency/jitter and speed drop using VPN.
Other solutions might be to use IPv6, tunnel IPv4-over-IPv6, use a different protocol that your VoIP protocol supports (IAX, SCCP), investigate SIP ALG, etc ....
Or investigate with your VoIP provider about ALG:
"SIP ALG is the session initiation protocol application layer gateway. This technology, which is also called an application-level gateway, is available on most commercial routers, and it helps users more reliably initiate SIP calls, even when behind a LAN with a secure firewall configuration. The ALG is a network address translation (NAT) tool that changes private IP addresses and ports into public IP addresses and ports."
Hope this helps,
Ian.
VA3IAN