The (root) certificate from the company you are trying to federate with is not available.
And by root certificate i mean the CA the company has accuired their certificate; Comodo, Baltimore Cyber Trust, Go Daddy etc.
There are 2 ways to resolve this, find the sipfederationtls SRV DNS record like this:
nslookup -type=SRV _sipfederationtls._tcp.microsoft.com
SRV hostname = sipfed.microsoft.com
Now you can try to get a certificate by guessing webmail domain names because the certificate at https://sipfed.microsoft.com:5061 doesnt return the certificate that you want.
An easier ways is to download the RUCT tool (Remote RU Troubleshotter) found here
Type the domain of the company you want to federate with and select the sipfederationtls SRV record, and on the Certificate Information tab click Go.
After finding the domain you want to federate with you can install the certificate with one mouse click in the local trusted certificate store on the Lync EDGE server.
You can easily find the imported certificate chain in the local trusted root store.