I have been informed by my webhosting provider the mails server that send and receives mail from scripts has been put off for security reasons. As such users of my website are unable to receive notices they have a message in their mailbox.
Isn't there anything they can do to protect the mail server without having it turned off?
Any comment or help how I can get this resolved is greatly appreciated.
They could just mean that you have an insecure script on your site which is allowing spammers to use your site to send spam to other people. I would ask for a full explanation of what is wrong and what you have to do to fix it.
I see way too many exploitable php and cgi mailers to believe the hosting company is just too stupid to know what they're doing (at least, believe it right away).