Gosh. For some reason, the "right answer" I expected to see was "do not try to validate the address; just send the e-mail and handle the bounce if it fails". There is a whole other layer which is very good at handling incorrect or undeliverable addresses.
The solution involved creating an entire cache/hash layer on the client using local storage.
At the end of the presentation I had to try to be as respectful as possible when I asked why basic browser caching and content expiration weren't enough. Apparently it wasn't even considered -_-