How connect Outlook to Office 365 without change the MX record of the domain yet

Inside ADSIedit under the ProxyAddresses field is correct.

You want the primary one to be preceded by SMTP: in all caps. In this case set it as SMTP:user@domain.com

The secondary/tertiary ones should be preceded by smtp: all lowercase. In this case set it as smtp:useralias@domain.com

Make sure the mail attribute in their user account in AD (the one on the General tab that says "E-mail") has the user@domain.com email address as well.

After a dirsync it should show an additional proxy address synced over as the "onmicrosoft.com" one but with lowercase smtp:

Also note, that if your domain hasn't been "verified" in Office 365 then it will revert back to using the onmicrosoft.com address.

Let me know if that works for you.

The problem here is how Exchange itself works (O365):

However mails sent from inside office 365 addressed to users with accounts in 0ffice365 continued to appear in office 365 mailboxes, and are not routed to the mx mail server (google apps), and thus are not appearing in google apps mail mail boxes.

This is to be expected. Exchange isn't going to send email to an external MX record for example.com if their email address is bob@example.com associated with a mailbox on the Exchange Online Org for your Office 365 domain. The routing of the email will dictate that the user is local and should be treated as such.

You have a couple of options as I see it:

Option #1:

Assuming you are using 2 distinct email domains for O365 and Google Apps you could have individual mailboxes on O365 forward any incoming email to the external Google Apps domain. I know you said your MX records go to google apps so you are probably only using a single domain name, but you could look at forwarding it to their gmail associated address instead and then setting their primary email address for new emails and replies to their real company domain email address.

In this instance the example would be:

Email to bob@domain.com > google apps mx > Office 365 route > Office 365 forwards email for bob to bob@gmail.com > google apps receives email and delivers to Bob > when Bob replies he chooses to reply as bob@domain.com instead of bob@gmail.com

Option #2

Like O365 support said, you can look into setting up the Internet Relay Domain option. What they were referring to is called Shared SMTP Namespace. I've never done it with Google Apps, but the concept is the same with them overall I would presume.

However, the issue you are running into is probably because you have actual mailboxes instead of contact email addresses only for those users. They can't have actual mailboxes on the Exchange/O365 server itself, just an O365 user ID with a contact email address.

But you'll also have to setup such a thing on Google Apps side somehow to (again not familiar with how they do it)...because otherwise you'll end up with a loop. You'll need something on their side that says "check for mailbox and if not found send to O365".

The flow would work like:

External Email to bob@domain.com > google apps receives and checks for local mailbox. If found, deliver...if not > Office 365 route > O365 delivers to mailbox there.

Office365 user emails bob@domain.com > Office 365 finds no Exchange mailbox but does see bob@domain.com as a contact > Exchange Online has the Internet Relay Domain setup for domain.com and the next hop set back to send outbound to the MX record > google apps receives email and delivers to Bob's mailbox locally on Google Apps.

Again, you'll need to make sure that Google Apps knows to check for bob@domain.com mailbox locally before sending everything else on to O365. Otherwise it will cause a mail routing loop.

Hope that helps.