We're trying to call their regular telephone line from our VoIP service
I assume that there are no similar problems calling from a regular landline. It sounds as though it might be a routing problem with either your VoIP provider or one of the carriers that it uses to complete the call.
The VoIP providers don't have their own direct connections to every central office in the country. They'll just send the call to the nearest suitable point and then hand it over to a regular phone company to complete the last portion (e.g. if you were calling a number in, say, the depths of rural southern Ga., they might send it as far as Macon, Ga. or Tallahassee, Fla. and then hand it over to BellSouth to complete). Sometimes the VoIP service will hand the call over to aanother long-distance carrier to complete (AT&T, MCI, etc.).
If a telephone switch anywhere along the way is not properly programmed, then you can encounter problems if the call takes that particular route (which it might do on some attempts but not others). If you get a recording ("Your call cannot be completed as dialed....") then the recording ID at the end will sometimes tell you where the call failed and with which company, but "dead air" symptoms aren't very helpful of course!
Your best bet is to contact your VoIP provider and explain the problem, giving the area code and prefix (first three digits of the number) you are calling. That will be enough for them to check the routings.
