I would imagine you could do this legitimately by connecting to each addresses SMTP server and starting an SMTP session, going as far as giving the address the message was for but resetting and quitting the session before sending an data. assuming the responses until that point had been 250 OK you could assume the address was valid.
the wikipedia SMTP page gives an example of an SMTP session, the test session would be the same up to the DATA command where you would send RSET then QUIT instead of feeding in an actual email.
The problem would be that SPAM blacklists use "honeypot" addresses that an only be acquired by scraping websites. They assume that should you send one of those addresses a message you must be a spammer and may ad you to their blacklist. The above test would not filter these addresses there is no way you could.
UPDATE I looked at the link you gave after I wrote the above. I wasn't expecting them to give such a detailed account of their process. Step 5 will be as I have detailed above. The other steps seemed sensible. The pricing seemed fair.