Is it possible to separate the email hosting for my domain into a couple of different hosts?
For example company.com has emails going to Google (apps for business) and Microsoft Online Services (exchange). Employee A's inbox is at Microsoft online services as [email protected] while Employee B's inbox is at Google as [email protected].
This is possible, but not completely independently. You need to have one primary mail provider which accepts all of your mail. Then configure mailboxes there to forward emails to another account.
For example, set up company.com at Google, and a new domain, company.net at Microsoft. Have Google forward all emails for [email protected], to [email protected]. Finally, set up the [email protected] account so it can send emails with the From address of "[email protected]".
The reason you have to do it this way, it the way email is routed around the internet. Email routing is per-domain, with one or more mail servers listed in DNS as being responsible for email. However, in DNS you specify which of your mail servers has the highest priority, and which others should only be tried when the primary is unreachable. Your secondary mail servers will then forward all mail received to the primary, which is responsible for putting email into a particular user's mailbox or forwarding it on to another address.
There is one alternative to this, if you're willing to run your own mail server: You could conceivably run a mail server on your own network which accepts all of your email for company.com, and then routes mail for individual mailboxes to specific destinations (Google or Microsoft). However to the best of my knowledge, Google and Microsoft don't offer this solution for you so you'd have to run your own mail server to achieve it.
The most simple solution when using Google Apps (like in your case) is to enable dual delivery in Google Apps.