Moved hosting - Unable to send or receive emails from site

Zen 1.5.1
Hosted on linux server
Email worked fine prior to moving hosting
send from known domain is on

But since moving we can't send email from zencart (neither admin nor contact page)

Sending email from admin

Using php
we get
Gateway Time-out

The gateway did not receive a timely response from the upstream server or application.

Using sendmail
we get
Email Error: Could not execute: /usr/sbin/sendmail

Using Sendmail -f
we get
Email Error: Could not execute: /usr/sbin/sendmail

SMTP
we get
Email Error: SMTP Error: Could not connect to SMTP host.

SMTPAUTH
we get
Email Error: SMTP Error: Could not connect to SMTP host.

QMAIL
Email Error: Could not execute: /var/qmail/bin/sendmail

I have set up dozens of Zencarts over the years and have never had any issues with th emails pretty much the PHP method has worked first pop.

This hosting does have the email working through "Microsoft hosted Exchange" rather than the normal linux mailboxes

The only mention in php info of mail that i can see is below

sendmail_from no value no value
sendmail_path /usr/sbin/sendmail -t -i /usr/sbin/sendmail -t -i
SMTP localhost localhost
smtp_port 25 25

any help would be appreciated

And yes i am going to contact the host

iinet.net.au

But just wanted to see if there was a simple fix tht i had overlooked

My initial reaction is your host has disabled php msil function to avoid spamming

in the admin
Tools-> Server/Version Info

What is the value for "sendmail_path"

Ok well this morning it all seems to be working fine

@bislewl I actually put that path in the first post

sendmail_path /usr/sbin/sendmail -t -i /usr/sbin/sendmail -t -i

It is still identical, I have no clue why it is working now when it wasn't earlier, the setting are identical

But all is good