Federation issue between Lync on-prem 2013 and Lync online

I work for a managed service company (tech.com). We are on Office 365 and use Lync Online. We have a client (companyA.org) who has an on-premises Lync 2013 environment setup. Client has us added as one of their allowed domains in the federation section with a domain name FQDN of tech.com and an access edge service FQDN of sipfed.online.lync.com. We have open federation on our end in Office 365. Communication between us and the client works properly. The client also has federation set up with another company (companyB.org) that's also on Office 365 using Lync Online. CompanyA has CompanyB added as one of their allowed domains in the federation section with a domain name FQDN of companyB.org and an access edge service FQDN of sipfed.online.lync.com. I've seen (not touched, because they're not a client of ours) the O365 settings for CompanyB and they have federation open to all domains except blocked ones.

CompanyB users cannot initiate a chat with a CompanyA user. When they try to, the companyB user gets the following error message:
--- This message wasn't sent because <companyA contact> doesn't have permissions on your organization's network, or because the address is incorrect. Please contact your support team.---
However, if a companyA user initiates the chat, their message gets through and then they can both chat back and forth with no problems whatsoever.

I've pretty much exhausted all my options on the on-prem Lync environment:
- I tried adding LyncOnline as a hosted provider with an FQDN of sipfed.online.lync.com but starting with 2013, it will not let you have an allowed domain and a hosted provider with the same FQDN.
- I tried removing the allowed domains and adding the hosted providers, but that just made things worse as we couldn't see status information anymore.
- I tried enabling partner domain discovery, to no avail.
- I checked to ensure that all other federation settings were correct and there's nothing different from how tech.com and companyB.org are set up as allowed domains in companyA's on-prem Lync environment.

What I think is causing the problem:
After I checked and verified that both O365 companies are setup identically in the on-prem Lync environment, I began looking at other aspects of each one that I can compare to see where there's a discrepancy, if any. I found an article that said that in order to find the correct access edge service FQDN for a company, I can do an nslookup for the following srv record: _sipfederationtls._tcp.DOMAIN.COM. Low and behold, I found out that I get a proper reply (with needed info including an svr server of sipfed.online.lync.com) when doing _sipfederationtls._tcp.tech.com. However, when I do the same lookup for _sipfederationtls._tcp.companyB.org, I get back the following: <LOCAL SERVER> can't find _sipfederationtls._tcp.companyB.org: Non-existent domain. I did the same lookup for all of our other clients who are on Office 365 and use Lync online and got the correct result back (identical data as the tech.com lookup). Also did the same for all companies on lyncdirectory.com that have an SIP access/server name of sipfed.online.lync.com listed and got the correct results for all of them, except 1 (kirbside.us). I then found this article (https://technet.microsoft.com/en-us/library/gg412787.aspx) that states the required DNS records for Lync 2013. About halfway down the page there's a section labeled RECORDS REQUIRED FOR FEDERATION with only 1 entry listed, for this exact DNS record that companyB seems to be missing. This strongly leads me to believe that this is what's causing the problems but I don't know enough about Lync definitively make that call.

Any help/clarification on this would be greatly appreciated. Thank you for your time.
Who is Participating?

[Product update] Infrastructure Analysis Tool is now available with Business Accounts.Learn More

I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Not my strongest area either (Lync), but when setting up a domain with Office 365 you choose the purposes it's to be used for (Exchange, Lync, etc.) and they tell you which DNS records need to be created.  I wouldn't spend time on looking at other issues until I verified that all their DNS records have been added as requested by Office 365.
Lync records

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
Mai Ali (MVP)Senior Infrastructure ConsultantCommented:
Verify from Firewall ports between lync online and lync on-premises. Check the Lync Configuration
Also check below link for troubleshooting this issue
TechBostonAuthor Commented:
Footech - Thank you for that info, I will look in to that.

Mai Ali - Thank you but I've been directed to that article via my various google searches for the solution to this issue and it has not helped me unfortunately.
TechBostonAuthor Commented:
Found out that they did have this srv record, but it was set to _sipfederationtls._tcp.@.companyB.org. Having @ in the middle is not only very rare, but it also does not follow Microsoft's instructions for creating this record. They've removed @. from the record and we've restarted the Access Edge service on our end just to be sure. Will test tomorrow and let know how it goes!
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Chat / IM

From novice to tech pro — start learning today.