From past experience, I would recommend trying to send e-mail from your web hosting service in another manner: one that you know should work.
Not knowing who you are hosted by, I cannot give specific advice. But if you have access to cPanel, try using the Webmail feature (Mail-Webmail) to send an e-mail to yourself at your Internet Provider’s e-mail address for you NOT to your web site that goes through your web hosting service.
This will determine if your web host has problems sending e-mail, as opposed to it being a WordPress problem.