I had the same experiences with Hotmail and sisters.

Only one of our users, instead of setting her notifications, she found an easier way and reported all incoming emails from our site as spam.

We could never heal the damage and return to a normal state with Hotmail again and started using a SMTP provider.