I believe a CTI system using ISDN calling based service can quickly return a status code that the number is either valid/invalid before the destination begins to ring.
One vendor is Katalina systems, their product is called VoiceGuide and they have a dialling out module that may give you what you want. see www.voiceguide.com.
Just export the calling list to the dialler (csv file) and review the call status after processing.
If the list is very large, it may justify purchasing a system to do this. The rate of calling depends upon the number of lines installed/availble. You might require some custom modifications to abort the call after obtaining the status. Katalina should be able to help. I am not sure if VoIP trunks can give you full access to the line status.