I think the CC providers charge merchants for these. Do you know that to be incorrect? If I'm correct this means that it now costs email providers cents per account per month, which just took an expensive turn for the worse.
If it doesn't work that way I bet Visa amends their merchant agreement to start charging -- they aren't in the business of doing millions of identity verifications per month for free.
Oh, you definitely pay for the privilege of submitting Auth requests. You have to have a merchant account with the card issuer. The systems I've worked with went through a third-party gateway system which connects out to all the different card issuers. It's definitely not cheap to set up. I'm not sure if there's a per-request charge or not. I wouldn't be surprised either way.
I think there would actually have to be some money changing hands. Five dollars would be enough to throw out the spammers and still be a small enough amount to keep customers happy. This is assuming that their e-mail is extremely important to them.
I'm thinking Google and Microsoft can't do this. Perhaps there is a niche opportunity here?