Well, pretty much the only way to guarantee that a number is working is to call it and see what happens. I suspect Ken Rice has some experience in this area and I'd definitely like to hear it. If anyone else has thoughts I'd like to hear them as well.
P.S. - Why does the customer think that calling the number and playing a short message will take too long? Also, what is the customer's primary concern about the web leads having non-working numbers? Is it because they have humans manually dialing them and it's a waste of time when the person comes across a bad number?