Warning mail to sender when seding to hotmail

Hi there

We have our servers IPs at OVH IP address-space and from time to time,
when we send emails to a small, particular set of very-well-known
domains owned by one very large corporation, there are periods where our
customer's emails go, by default, to the SPAM folder no-matter-what.
Under those periods I'm thinking of activating the sending of a
complimentary warning to the sender to let the recipient know they
should check the SPAM folder and brief guidelines to add them to the
list of safe senders.

What should be the best approach to accomplish this?