The answer from my Host:
"Thank you for your email regarding this matter. Per my investigation there were a pretty large amount of emails in the server mail queue due to an abuser that tried to send a very large amount of spam. We have disabled the abuser and the mail service should work without problems now. Feel free to contact us back if you have any questions. We will be more than happy to assist you."