I don't know about legality, but whenever I contact companies with unsolicited email (usually domain related) I always add a line to reassure them that they were hand chosen because the domain/service is relevant to them, the email was not generated from a spam mailing list and to contact me with any questions.
I'd imagine some recipients think it is just a ploy to confirm valid email addresses though.