As per Pekka's comment, most companies with a public API don't allow scraping in their terms of service, so it's quite possible that performing 4k GET requests to their website will flag you as a malicious user and get you blacklisted!
Their API is RESTful and seems simple and pretty well documented, definitely try to get that working instead of going the other way. A good first attempt after getting your API key would be to write a UNIX script to perform a reverse phone number lookup. For example, suppose you had all 4000 10-digit phone numbers in a flat text file, one per line with no formatting, you could write a simple bash script as follows:
#!/bin/bash
INPUT_FILE=phone_numbers.txt
OUTPUT_DIR=output
API_KEY='MyWhitePages.comApiKey'
BASE_URL='http://api.whitepages.com'
# Perform a reverse lookup on each phone number in the input file.
for PHONE in $(cat $INPUT_FILE); do
URL="${BASE_URL}/reverse_phone/1.0/?phone=${PHONE};api_key=${API_KEY}"
curl $URL > "${OUTPUT}/result-${PHONE}.xml"
done
Once you've retrieved all the results you can either parse the XML to analyze the matching businesses, or if you're just interested in existence you could simply grep each output file for the string The search did not find results which, from the WhitePages.com API, indicates no match. If the grep succeeds then the business doesn't exist (or changed its phone number), otherwise it's probably still around (or another business exists with that phone number).