From your description, you have the following configuration:
IP network < -VoIP-> Gateway< -SS7-> PSTN switch
In SS7 there are standard 'cause codes' which are returned to provide indications to the equipment initiating the call. For a list of cause codes go here.
Now, there is likely something that the switch inserts in the IAM (Initial Address Message) when that certain group of 800 numbers is dialed that is not there in other IAM messages. When the gateway receives the IAM from the switch associated with that certain group of 800 numbers, in its response it is sending a Cause code = 111 Unspecified Protocol Error back to the switch indicating that it cannot process the call. The best thing to do here is the following:
If the gateway or the switch has protocol analysis built into it, get a capture of a successful call and an unsuccessful call (if neither product can capture a protocol trace, use an external SS7 protocol analyzer). Look at the contents of the IAM and determine what is different. You should then talk to the gateway manufacturer and pass them the traces to see why they are sending the 111 response. At the same time, you could see if you can pass the same traces to the provider to see if they can reconfigure the switch. Note that it is possible that the gateway is sending the 111 response because of something it receives on the IP side. You'll want to capture that side of the call as well in each case.