Getting a really large list of valid residential addresses in the united states is 100% completely trivial.
For example, all the registered voter databases are for sale or free (though generally only allowed to be used for "political purposes", and not "commercial purposes", if you get them from the state themselves).
> Was shown this address but it isn't valid
Wachtell, Lipton, Rosen & Katz would disagree with you: http://www.wlrk.com/
But perhaps you were referring to the fact that there should be a newline between the care-of and the street address?
c/o WLRK
51 West 52nd Street
New York, NY 10019
Even licensed vendors don't get the full list, they get an encrypted database of the address and a C library with which to query it. (Source: I worked for such a vendor and wrote code to interface with said C library.)