A customer of mine had this strange problem; they could not federate with two of their partners. All others were working just fine, whereas these two only gave the infamous “presence unknown” status. They even got confirmed that others could federate with these domains too, just not them.
I remembered from a previous event that Windows Server 2008 R2 root certs in some cases may be corrupted, so this was my primary suspect.