We use Office 365 for e-mails etc.

We are able to receive e-mails fine into ServiceDesk Plus On-Demand but every time the system tries to send an e-mail, it comes up with the following error:

Mail sending failed.Authentication failed

The same account/credentials are being used for receiving and sending e-mails so there is no issue with the password etc.