When communicating to hosted companies in Office 365 from an On-Premise Lync environment, I had begun seeing the following symptoms:

1. Presence defaulted to Unknown for federated contacts:
   
2. When joining someone's meeting or sending them an IM, I would see the following:
   "When contacting your support team, reference error ID 403 (source ID 239)."
   
3. Inside of event viewer, I saw:
   403 Forbidden
   ms-diagnostics-public: 1034;reason="Previous hop federated peer did not report diagnostic information";Domain="othercompanydomainon.com";PeerServer="sipfed.online.lync.com"
   

Solution:

Interestingly enough, even though you have an On-Premise Lync environment, it appears that Office 365 will tie back to your account for some settings.  In my case, I had not enabled federation to other PIC providers on Office 365.

To resolve the issue, please follow the steps below:

1. Login to the Office 365 Admin Portal
2. Click on Manage Lync
   
3. Click on the External communications tab and ensure the following settings:
   1. Domain federation mode: Turned on for all domains except blocked domains (you can switch to the other mode, just keep in mind you will have to whitelist every domain you are enabling communication with)
   2. Public IM connectivity mode: Enabled
   3. 
4. Next, head over to the Lync Online Control Panel for your on-premise Lync deployment.
5. Select the Federation nand External Access tab and then select SIP Federated Providers
   
6. Ensure you have created a rule for the provider LyncOnline that is federated to sipfed.online.lync.com
   
   1. To create the provider via the Lync Server 2013 Control Panel
      1. Select New... and then click Hosted Provider
         1. Enable communications with this provider: Checked
         2. Provider Name: LyncOnline
         3. Access Edge Service (FQDN): sipfed.online.lync.com
         4. Click Commit
   2. To create the provider via PowerShell, execute the following command:
      1. New-CSHostingProvider -identity LyncOnline -ProxyFqdn sipfed.online.lync.com -Enabled $True

Wait a few minutes for the changes to take effect, exit out of your Lync client on your workstation, reopen and you should now be able to communicate to your federated partner.