Sorry, but to me, the VIA header looks correct given what you have displayed. The VIA is used to indicate "the path or proxy" by which the invite traversed. The connection IN (C) underneath the SDP should be reflecting the public IP that the provider seeks.
When you initiated the call, the data flowed from the phone to the system and as a result, the initial "VIA" (should of) had the address of your phone. Then the system, communicated with the provider, which the "VIA" should of had the IP of the system, but the connection info should have been the IP as set by the advanced parameters which would be your public IP.
So, the path the routing took is the VIA and conversely the provider should be providing the same thing in reverse. A proxy can alter the VIA if one is set. The VIA used in conjunction with the other IP related headers or values such that it eliminates the need for any resolution or lookups (other than to the provider in the initial invite) as each step is spelled out implicitly in the flow.
In response to your other post about the provider not needing registration -
This may be true, but this does not mean that they may not be looking at the stream and reacting accordingly. I am somewhat surprised about the issue as most providers who do not require registrations require a fixed IP at sign-up or activation and that IP is already a part of their database. If they can match, then all is good. I use a provider who does not require registration, but I use it anyway as it helps to know whether the trunk is there or not proactively - shows green or red. I had suggested using it so that regardless of their need, it would just reinforce the path you needed. I use "specify" and insert the public IP. Again, because they may not require it does not mean that they don't support its use.
Perhaps your provider does indeed need something different which is when I suggested the need to look at other optional settings, but only after eliminating those that would normally be used. I still suggest changing the VoIP provider registration as suggested and trying as there is nothing to lose.
Can you at least share who the Provider is? Others may be using and can better advise?