From our experience the problem you describe is usually due to the fact that the provider does not honor the registration contact.
i.e. Instead on sending the inbound to sip:xxxxxx@us.voxalot.com they send it to sip:9876512344@us.voxalot.com where 9876512344 is your provider account.
We recently help a local provider
MyNetFone - Your VoIP Broadband Phone Service - Leading Australian VoIP Service Provider for Residential VoIP & Business VoIP Solutions resolve this problem.