http://www.theverge.com/2016/6/1/11827310/microsoft-outlook-hotmail-email-spam-june-2016
http://www.cbronline.com/news/enterprise-it/software/microsoft-claims-to-have-fixed-issue-which-saw-outlook-and-hotmail-flooded-by-spam-4911717
So, in your case, it sounds like improvements in hotmail/outlook is now affecting what used to be borderline "legitimate Email".
Is your Moodle is using an STMP server which has appropriate MX, SPF, DMARC, etc. type records in DNS to verify the sending mail server is a valid sender?
If you are **not** using an SMTP server, Moodle uses it's built in PHPMailer.
So the mail leaving Moodle shows in Email headers that the mail originated
from your Moodle server - which probably doesn't have MX, SPF, DMARC records etc. in DNS. Thus mail from your Moodle doesn't pass whatever checks hotmail,etc. is doing using to decide if it should accept the mail from your server.
Your options at this point:
1. route mail though a valid SMTP server that will relay mail from your Moodle.
2. ask users to use other Email addresses.
SMTP server setup:
https://docs.moodle.org/31/en/Messaging_settings
Need an SMTP service?
SendGrind is one that offers a fREE 12.000 messages a month service.
Don't work for them ... don't use ... just trying to anticpate the next question related to setting up an STMP server.
https://sendgrid.com/marketing/smtp-server/
'spirit of sharing', Ken