Well, the title says it all! You will have to excuse my lack of use of images, I'll have to get back to this post and add some later on, but at the moment you'll have to make do - I'll try to be as descriptive as I can!!

I'm assuming that you've bought some Office 365 Licenses, and also that you have an Exchange 2010 installation on-premises. I'm also assuming that you've got an Internet Domain Name set up internally (i.e. contoso.com, not contoso.local). Let's get started:

At this point you are faced with three options, as described in this MS article: http://community.office365.com/en-us/w/exchange/514.aspx?CompanyType=CompanyTenant&DapEnabled=0&HasLiteSKU=0&HasAdminPermissions=1

Hybrid routing implies the extra cost of buying FOPE (Forefront Online Protection for Exchange) licenses, so although it's the best solution out of the three it's a no-go for now. Of the other two, the one that makes more sense is a decentralized shared address space, where email flows to cloud recipients through the on-premises server and sent from cloud recipients to Internet recipients directly from the cloud. A centralized shared address space would only make sense if strict compliance was to be enforced by a security protocol like SOX or ISO.



Implementing a Decentralized Shared Address Space scenario


Setting up Domains and DNS Records 

1. Sign in to the Microsoft Online Services Portal with your Office 365 Administrator Credentials
2. On the Admin page, under Management, click Domains
3. Click Add a domain
4. Type the name of the domain you would like to add (e.g. itguy.gr)
5. Click Next
6. Click Verify domain
7. Add a TXT record on your public DNS system

Now comes the part where you choose your newly added domain's intent, i.e. what you'll use it for. For the moment let's choose just Exchange Online, for two reasons: SharePoint Online must be added in a separate process and for Lync Online you cannot use a domain that's already set up on-premises in a hybrid scenario.

On the second step of this wizard comes the truly confusing part; You'll be presented with a table with 3 types of DNS records: TXT, MX and CNAME. You can safely create the TXT one, but for the other two, if you create them you'll be effectively cancelling out the DNS records that have your on-premises system working!!! Think about it: you already have an autodiscover.yourdomain.com CNAME record, or else auto-configuration wouldn't work in your on-premise system. Similarly, if you overwrite your @.yourdomain.com MX record, say bye-bye to incoming mail to your on-premise Exchange system. So here's what you should do for the example domain we all love, contoso.com:

CNAME Alias: autodiscover.service.contoso.com
TTL:3600
Destination Host: autodiscover.outlook.com

MX Mail domain: service.contoso.com
TTL: 3600
Preference: 10
Mail server:  contoso-com.mail.eo.outlook.com

You're welcome!!


Preparing your on-premises organization for Office 365


Let's kick this off by saying that your on-premises Exchange 2010 Server(s) should all be on SP2. This means the EDGE server(s) as well.

First step will be to update your exchange schema for hybrid deployment, and mind you, the domain controller on which you update your schema must be a 64-bit machine and be included in the same AD site as your schema master.

So, open a command prompt, navigate to the directory location of your Exchange Server 2010 SP2 binaries and type setup /prepareAD

Now it's time to deploy your Federation Server Farm. I'd normally opt out of creating a server farm as most of my clients' environments use clustered Hyper-V servers so the individual VMs are safe enough, but in this instance ADFS 2.0 is an ultra-light application that you can set up on any domain-joined server. Effectively, the only pre-requisite is that these 2 servers must not utilize IIS for port 443 (HTTPS). That's all!

There's a great step-by-step article here on how to set up your ADFS server farm:

http://onlinehelp.microsoft.com/en-us/Office365-enterprises/ff652539.aspx

But we'll do a quick step-by-step nonetheless:



Deploying a Federation Server Farm


What you'll need:

• Two Windows 2008 or 2008 R2 hosts joined to your domain. One will server as the primary server (the one you will install ADFS first) and the other as backup.
• One IP address that will serve as your NLB cluster IP Address
• One DNS A record (in your internal DNS servers) in the form: sts.yourdomain.com
• One trusted third-party SSL certificate

Let's go:

1. Install the Network Load Balancing Feature on both servers and set up an NLB cluster. Make sure you define a port rule just for HTTPS (TCP port 443)
2. Go to the primary ADFS server (i.e. the one you will install ADFS first), go to IIS Manager and create a certificate request. Tho points to pay attention to:
1. As a certificate common name use: sts.yourdomain.com
2. As a bit length use: 2048
3. Now use the certificate request you created to obtain an SSL certificate from a third-party provider. (hint: if you're creating a lab or you just don't care too much about security give www.startssl.com a go... one year SSL certificate 100% free!!!)
4. Install the certificate in the primary ADFS server's IIS manager. Also go to bindings, and select the newly-imported certificate for HTTPS
5. Now extract the certificate with its private key (.pfx) and repeat step 4 on the secondary ADFS server's IIS
6. Create an ADFS service account
1. Create it as a user in Active Directory Users and Computers
2. Make sure "User cannot change password" and "Password never expires" is selected
3. Set the SPN of the service account as described here
7. Install ADFS 2.0 on both servers
1. Obtain installation package here
2. On the Server Role page of the ADFS 2.0 setup wizard, make sure you select "Federation Server"
3. Install the ADFS Update Rollup 1
4. Install Microsoft Online Services Sign-in Assistant
5. Install Microsoft Online Services Module for Windows PowerShell
8. Configure First Federation Server in Federation Server Farm
9. Add Secondary Federation Server to Federation Server Farm

Enabling single sign-on:

Careful! The first three steps are not included in any guide !!

• One Windows 2008 or 2008 R2 server
• Access to modify your external DNS records
• The certificate you used on your internal ADFS servers
• A working DMZ Topology
• Appropriate rules on your corporate firewall

Here we go:

1. First of all, configure your Windows server, position it on the DMZ and make sure there is connectivity both to the Internet and your internal network
2. Install the IIS Role with the default options, import the certificate you installed to the internal ADFS servers, and configure the bindings for port 443
3. Add the respective Host Name and IP address of the ADFS NLB Cluster you created earlier to the ADFS Proxy server's Hosts file
4. Create a new A record on your public DNS server with the name sts.yourdomain.com (exactly like the one you created on you internal DNS servers) and point it to the public IP address you will use for your ADFS Proxy
5. Configure your firewall so that HTTPS requests on this IP will be forwarded to your ADFS Proxy
6. Make sure you can:
• ping the load-balanced internal ADFS server farm (sts.yourdomain.com)
• browse to this link: https://sts.yourdomain.com/federationmetadata/2007-06/federationmetadata.xml
• On IE 9, hit the 'Compatibility View' button, then you should be able to browse the XML contents
7. Now run the ADFS 2.0 setup and select Federation Server Proxy
8. Once completed, make sure the "Start the ADFS 2.0 Federation Server Proxy Configuration Wizard when this wizard closes" check box is selected and click finish.

Once the AD FS 2.0 Federation Server Proxy Configuration Wizard starts, do the following:

1. On the "Specify Federation Service Name" type: sts.yourdomain.com, i.e. the exact same name of the internal load-balanced ADFS server farm we configured earlier
2. The "Use an HTTP proxy server when sending requests to this federation service" IS STUPID!!! Why on earth would we need yet another proxy, to proxy our proxy's requests!!!! Make sure this check box remains unselected and hit "Test Connection". If network connectivity is working you will get a "The specified Federation Service was contacted successfully" message.
3. Hit Next, and you're prompted for the logon credentials for the internal ADFS server farm. Remember the ADFS service account you created? That's the one. You're supposed to enter the credentials in the form
   
   yourdomain\adfsaccount
   password
   
   But first go to Server Manager's Main Page, click on "Configure IE ESC" and turn it off for both users and administrators. Don't, and you'll get "unable to establish a trust between the federation server proxy and the federation service" errors
4. On "Ready to Apply Settings, click on Next and watch the magic happen!

• Log on to a computer that sits outside your corporate network (so that it will be directed to your ADFS Proxy server
• In an Internet Explorer window, type https://portal.microsoftonline.com
• In the User ID field, type your corporate username (e.g. user@yourdomain.com)
• The web page should update with the "You are now required to sign in at yourdomain.com" message
• Click the sign-in link and in the sign-in page and enter your domain credentials
• If this takes you to the Microsoft Online Services Portal home screen, then you can pat yourself to the back; the ADFS system you just configured works
• If not, re-check what we've done so far and that you haven't skipped a step. You can also check Adam Conkle's great post on this TechNet thread: http://social.msdn.microsoft.com/Forums/en-US/Geneva/thread/bd815b4e-70be-4f1c-ac7f-a5e9ac5aea02?prof=required

Now to create a Federation Trust:

1. On EMC, go to Organization Configuration and on the Actions pane, click on New Federation Trust
2. Click on New and then on finish and you're done

Last but most definitely not least, we need to create a Hybrid Configuration:

1. Right click under Organization Configuration and choose New Hybrid Configuration
2. Go through the 2 steps of the wizard and click on finish
   This was too easy, now comes the tricky part
3. Right-click on the Hybrid Configuration and choose Manage. The Manage Hybrid Configuration opens
4. On the credentials screen, type in the appropriate usernames and passwords. What I suggest you do is (since we've already synchronized Active Directory) to enable an Active Directory user that is member of the on-premises Organization Management role group, as a Global Administrator in Office 365. This way, you can use the same account for both fields
5. Under Domains, choose your hybrid domain
6. On the next step you will be asked to create a TXT record on your public DNS servers with a Record Value that is a lengthy string of alphanumeric characters. Check the box to confirm that the TXT record has been created
7. Next up, choose your hybrid on-premises CAS and HUB servers
8. Under Mail Flow Settings type the Public IP address of your on-premises Exchange server (i.e. the one on the public MX record), then type the FQDN of the HUB server you chose in the previous step
9. Mail Flow Security is pretty much straightforward, the third-party certificate is already there, and for the Mail Flow Path choose the first option (as discussed in the beginning of this article).
10. Click next but don't go any further just yet! If you continue you will most likely get an error and the wizard will fail with something like:

Execution of the Get-FederationInformation cmdlet had thrown an exception. Federation information could not be received from the external organization.

OR

Exception has been thrown by the target of an invocation

What on earth is wrong? Well, either the MRSProxy is disabled, or WSSecurity is disabled, or the MRSProxy is unreachable from the Internet.


Regardless of where exactly the fault lies, do all of the following:

• On your Hybrid Server's Exchange PowerShell, enter this command:
  Set-AutodiscoverVirtualDirectory -Identity ‘autodiscover (Default Web Site)’ –WSSecurityAuthentication $true
  to enable WSSecurity authentication for autodiscover on your hybrid server, and...
• On your Hybrid Server's Exchange PowerShell, enter this command:
  Set-WebServicesVirtualDirectory -Identity "EWS (Default Web Site)" -MRSProxyEnabled $true -MRSProxyMaxConnections 100
  The rule of thumb is that the larger number you use for the MRSProxyMaxConnections parameter, the less chances there are that a timeout will occur for large simultaneous mailbox moves.
• Create a new publishing rule for Autodiscover in your TMG server.
  To get your hybrid scenario working, you will need to set up an additional ISA/TMG rule pointing to the hybrid server, using the proper public names (don’t forget autodiscover), bound to the OWA listener. You need to allow All Users (as opposed to Authenticated Users), set authentication to “No Authentication, but users can authenticate directly” and configure the following paths:

• /EWS/mrsproxy.svc/WSSecurity
• /EWS/Exchange.asmx/WSSecurity
• /Autodiscover/Autodiscover.svc
• /Autodiscover/Autodiscover.svc/WSSecurity

After configuring the rule, you need to put it above all the other Exchange rules, making it the first matching rule when federation traffic hits ISA/TMG.



Now you're ready to go through with the wizard and bask in the glory of your success!!!

• We've configured our SSO domain with Office 365
• set up public DNS records
• installed an internal ADFS server farm
• enabled Single Sign-On
• configured Active Directory Synchronization
• installed our ADFS proxy on the DMZ
• verified the ADFS bit is all interoperable
• configured our on-premises Exchange 2010 hybrid server for Office 365

Only thing left to do is to move our mailbox(es) up to the cloud!

1. On the EMC console, go to the on-premises node --> Recipient Configuration --> Mailbox
2. Right-click the mailbox you want to move and choose New Remote Move Request
3. On the Connection Configurations windows, under "FQDN of the Microsoft Exchange Mailbox Replication service proxy" type the Internet FQDN of your hybrid server. Definitely consider typing in a domain admin credentials for this test.
4. Under Move Settings, for the Target Delivery Domain browse for "yourdomain.mail.onmicrosoft.com"
5. If you followed this article to the letter, the move should go without a hitch.

You can follow the progress of the mailbox move from Recipient Configuration, Move Request in the EMC console (the Office 365 federated forest you added earlier)

1. On the EMC console, go to the Office 365 node --> Recipient Configuration --> Mailbox
2. Observe that the mailbox you just moved appears with a green arrow. This means that a move request exists for this mailbox (albeit a completed one). You will need to go to "Move Request" underneath select the move request and click on "Clear Move Request". This will enable you to move the mailbox back to the on-premises organization. 
3. Now right-click the test mailbox and click New Remote Move Request
4. On the Connection Configurations windows, under "FQDN of the Microsoft Exchange Mailbox Replication service proxy" type the Internet FQDN of your hybrid server. Definitely type in a domain admin credentials for this test, then consider using delegated permissions
5. Under Move Settings, for the Target Delivery Domain browse for "yourdomain.com". For Remote Target Database, type the on-premises database you want to move the mailbox to. Contrary to what other guides might say, just type in the database name without the server name.
6. This should be enough to get the test mailbox moving back to your on-premises exchange organization.

Finally, it's time to test email flow. Test for all possible cases:

• From Office 365 users to Internet (external) recipients
• From Office 365 users to on-premises recipients
• From on-premises users to Office 365 recipients
• From Internet (external) email users to Office 365 recipients

One potential issue here that has emerged on several of my clients; If you are using TMG with Exchange Edge collocated on the same server then you might have an issue with your Edge Receive Connector. By default, TMG controls (i.e. blocks) all changes made on the Edge Role. So if you have E-Mail Policy Integration mode enabled on your TMG server chances are that the creation of the Receive Connector for Office 365 on your Edge Server has been blocked by TMG.

Check for EventID 31506 from Microsoft Forefront TMG Control service in the Application Log. If you see this error and the Receive Connector is then this is what you should do:

• On the TMG Management Console, to to Troubleshooting and on the Tasks pane click on "Control E-mail configuration Integration"
• Set the status to "Disabled" and enforce the policy.
• Go to Forefront Online Protection for Exchange Administration center and make a note of the IP addresses listed under "IP addresses to configure on your firewall".
• Login to https://portal.microsoftonline.com/ with a Global Administrator account
• Click on Outlook
• On the upper right-hand side of the Outlook page click on Options and then "See All Options"
• On the upper left-hand side click on the drop-down list arrow right from "Manage Myself" and under "Select What to Manage" click on "My Organization"
• Go to Mail Control and on the right-hand side of the page, under Forefront Online Protection for Exchange click on "Configure IP safelisting, perimeter message tracing and email policies"
• This takes you to Forefront Online Protection for Exchange for your organization. Under Information, click on Configuration.
• Copy-paste the IP addresses and subnet ranges to a text document, then arrange them in a comma-separated way, like so:
  12.12.12.0/24, 14.14.14.0/26, 34.23.34.156
• Now open the Exchange PowerShell on the TMG/Exchange Edge server and type the following command:
  New-ReceiveConnector -Name "From Cloud" -Usage Internet -RemoteIPRanges <FOPE Outbound IP Addresses> -Bindings 0.0.0.0:25 -FQDN mailserverexternalFQDN.yourdomain.com -TlsDomainCapabilities mail.messaging.microsoft.com:AcceptOorgProtocol
  where <FOPE Outbound IP Addresses>, copy-paste the comma-separated list from the text document

This will create the receive connector and reinstate email flow from Office 365 to your on-premises organization




Fine tuning?

Now that everything's working you might want to do some fine tuning. This article has great info regarding the Mailbox replication Service. MRS is the service responsible for moving mailboxes, importing and exporting .pst files, and restoring disabled and soft-deleted mailboxes. So, depending on how you want to plan your mailbox moves and your migration to your desired hybrid model, you may want to tamper with the MRS configuration accordingly.