I would continue to press the provider. I had an issue in which voicemail would not answer, company greetings, voicemail, nothing worked and it drove me batty! The carrier fixed it, not sure what the resolution was but I think it had something to do with SDP negotiations. The only thing standard about SIP is that it is not standard. Have you done any packet traces?