Hello!
Several years ago I already got a postcard with a verification code to prove that my postal address is correct. And this was not a paid service but a large freemailer with thousands of customers. So, no it's not rocket science and yes it was already done this way in large quantities (by another service provider).
Best regards,
Karl-Josef Ziegler