Lots of businesses run their own email server. It's not that complicated.
The easiest way to do it is to buy an email server, you can use Exchange or you can use something like iMail or Kerio.
Install that on a server, get a static IP from your ISP, put the server behind a firewall, and point your DNS servers for your domain to it. Then generate an SPF record, and you should be good.
That's how many people do it. As a bonus, you don't need to pay $10/user per month for hosted mail, or deal with Exchange licenses, but you will probably want to back the server up from time to time. You even get webmail with it!
The advantage/disadvantage of this setup is that it's now up to you get to get yourself off spam blacklists and such. When BIG_EMAIL_HOST is having problems, there's nothing you can do but wait. But with your own servers, you are the one who gets to email the spam department of BIG_ISP to request removal, and then there's nothing you can do but wait.
If you know Linux, you can setup Postfix, but I did say 'the easy way'.