These instructions are great, however the one step that does not work on Exchange 2010, at least in the order provided is this:
"Remove-FederationTrust –Identity “Microsoft Federation Gateway”"
It gets the following error:
[PS] C:\Windows\system32>Remove-FederationTrust -Identity "Microsoft Federation Gateway"
Can't remove federation trust "Microsoft Federation Gateway". It's in use by the following organization(s): CN=Federati
on,CN=First Organization,CN=Microsoft Exchange,CN=Services,CN=Configuration,DC=domain,DC=local
+ CategoryInfo : InvalidOperation: (Microsoft Federation Gateway:ADObjectId) [Remove-FederationTrust], Or
gsStillUsingThisTrustException
+ FullyQualifiedErrorId : 7A9EB9BE,Microsoft.Exchange.Management.SystemConfigurationTasks.RemoveFederationTrust
+ PSComputerName : exchange.domain.local