For Office 365, if they can go to each of the mailboxes they went to be able to send from, and give them the ""Send As... "" permission to the email box you are using to authenticate with, you should technically be able to send as the other emails.
If they want to still use the local SMTP server, and not risk being blacklisted, they can relay it through a 3rd party mail server. (i.e: Amazon Simple Email Service), which will allow them to verify their domain, and also add DKIM verification. Now, all mail from Sage will relay through the local SMTP, via SES then to the recipient, with all the correct headers. and you can then use any number of ""From"" email addresses.