I have not used INSTR, but tried a generic message to those emails in our system. We ran it from a dummy email account.
In the end it was not worth the pain, so we had customer service at time of order verify the contacts e-mail each time. A pain for them, but with so many companies neededing e-mail confirmation it was eaiser then generating paper and mailing.
Perhaps it is time well spent after all.