I am working part time for a small company, they have about 40 employees that use the email everyday for work and recently they have acquired a MS account for 10 employees that use it mainly for teams with customers but also sharepoint, etc.

To buy an MS account for each of the 40 would be too expensive and necessary because the other 30 only really use email in the day to day work.

So what I did initially was to follow this Microsoft doc: https://learn.microsoft.com/en-us/exchange/mail-flow-best-practices/how-to-set-up-a-multifunction-device-or-application-to-send-email-using-microsoft-365-or-office-365

So our MX register point to Exchange server and exchange relay it to the secondary email server where all those 30 accounts exists.

It was working fine until I we started to get this "Not delivered message" email returning with this error:

Error:	550 5.7.367 Remote server returned not permitted to relay -> 554 5.7.1 : Relay access denied

I talked to the support of this secondary email server and they told me they do not support this operation.

So I am looking for help in finding some server that would allow me to work like this. Do you happen to know some company you could recommend?