This is likely not a phone issue as the SIP provider is communicating at this level directly with the 3CX system. I suggest you look at the set-up for the provider. The first thing to check is whether there is a registration for the Trunk. This assumes that it is a register trunk and that your setting calls for a registration on both inbound and outbound calls. If not, it may show as registered regardless. If this is an issue, the 3CX system will tell you in the log that the trunk failed to register. If so, then look at the credentials being used.
You should look at the codecs set for the provider, the IP address set for 3CX and the SIP port. Internally on the LAN, there is no reason to have the phones set to a primary codec of g729 unless the LAN is saturated with traffic and even then, you should be looking at upgrading/fixing the LAN instead. Use g711u and then g711a and finally g729 for ViaTalk. Also keep in mind that with 3CX, the number of licenses available for g729 is only half of that for the others. This is due to the g729 codec still being protected by a patent which must then be licensed by 3CX.
As you did not indicate that inbound calls are failing, this still makes me wonder if the number being sent is correct. Say perhaps that one of the rules is altering the number using some kind of unsupported character. The rule is apparently sending it on, but there is something that Via Talk does not like and in reality, they should be able to monitor and tell what the issue is.
I assume that the provider is ViaTalk in the US, correct? If this is the case, I found a post on another board that, while somewhat old, provides a response to a question about the codecs that ViaTalk supports. In this post ViaTalk indicates that they only support g711u as they do not see a need to support others. If this is your provider, then make certain that the provider set-up has g711u (PCMU) at the primary codec and you may want to eliminate the other two I mentioned above from the list. As I indicated, it is somewhat old, but G711u is the main codec from most providers in the US.