Hi Kate,
Do you solve the problem? I used to have the same problem. At that time I asked my server host and they said my host was listed in blacklist. Therefore, I must use gmail to send emails in moodle. Would you like to use gmail to send emails in moodle? If so, I can help you.