Just replace your entire Microsoft email server with a self-hosted FOSS Linux email solution, where you can have unlimited email accounts.
Sysadmin
A community dedicated to the profession of IT Systems Administration
The cost of doing business means you should buy a license for each user that needs an account.
https://www.linode.com/community/questions/22605/can-i-set-up-a-smtp-relay-server-on-linode
SocketLabs, Mailgun
Hey so it seems like you don't really get licensing or 'too expensive' is just business speak for wanting it done free.
Exchange plan 1 licenses are minimally very very small licenses, but you can get even cheaper. You can even get exchange kiosk. Kiosk isn't designed for users, it's designed for things like an MFP then you're allowed to relay with an authenticated startTLS account setup on the MFP to connect to exchange Online.
However, if you don't use an authenticated account, you can still send internally. That way your inevitable compromised device doesn't spam the world with mail throttle Microsoft servers. However you can scan to your own internal staff. And by internal staff I'm guessing at more and more here but I'm betting you have two mail domains. Only domains in your exchange Online Admin centre which are added into the domains, will be 'internal'.
If you wanted hybrid you should do hybrid using the hybrid configuration wizard and it will connect your on premises exchange to your exchange Online using mail transports. You need to fix up a bunch of things to get that connected. But doing so will count the mailboxes which are on premise as 'internal' and unauthenticated mail will be allowed to relay to them.
But 40 exchange online only accounts with exchange plan 1 is hardly a few seconds of wage time per month in costs.
I'm guessing a lot here, but you said you have two different mail servers currently, online and on premise, I can only assume you've either got two different mail domains otherwise MX routing would be dead to one or the other. And I guess that because you said you're getting errors that only happen when you send mail to external users.
So...
You should do it in the cloud. I use gsuite and it isn't to bad in terms of cost. However, it is not free. You know what also is not free? Losing data and having reliably issues.