I found some kind of solution...
$claimManager = New-Object Microsoft.SharePoint.Administration.Claims.SPClaimProviderManager
$providers = @()
foreach ($cp in $claimManager.TrustedClaimProviders)
{
$providers += $cp
}
$provider = $providers[0]
$userId = $provider.Search("http://localhost", $null, $UserName, $null, 1).Children[0].EntityData[0].Key
The main issues with this solution:
Providers going through e.g. Azure ACS doesn't actually search to see if the user ID exists, but just returns a claim. This gives me the prefix for this ID provider, but I don't know if it's valid, thus I don't know if I should continue searching the other ID providers, or if I should just stop.
But I'm not sure if this is a configuration issue in ACS, or if it's an inherent weakness in the implementation of the Search method for identity providers in SharePoint.