That's a tough one. I believe Google gets a large part of their (US)
maps from the Census Bureau, which records a beginning/ending house
number range for each block. Google can then find "123 Main Street"
by finding the block that contains that number, and then interpolating
the range to get a location. Which means it will place "125 Main
Street" right next door, even though that address may not exist.
Google's Geocoder service returns a code indicating the type of
result, including "ROOFTOP" and "RANGE_INTERPOLATED". I would guess
that the latter indicates that Google cannot confirm that the street
number actually exists, and the former ("ROOFTOP") means something can
be seen in satellite view. But if you just bang every possible number
for more than a few blocks, you'll exceed the usage limit pretty
quickly.
The US Post office has a web service to give you the 9-digit zip code
from an address (
http://zip4.usps.com/zip4/welcome.jsp), and so far as
I can tell it will not return a result for an address that does not
exist. There exists a programmatic interface for which you can apply,
but your application is just the sort of thing that the Post Office
doesn't want (they want to help businesses that are just about to mail
something to an address). So you may not be able to get access that
way.
Last but not least, remember that empty lots almost always have valid
addresses, but no building. And many buildings (e.g., duplexes) have
two valid addresses but only one building.
Good luck!