Chris,If I understand well it appears the "Does Jane have a token for Service X?" question unnecessarily retains an unfortunate characteristic of NASCAR pages whereby only the most popular services are supported (thus encouraging the creation of a small number of large IdPs while excluding a large number of small ones).
A much more interesting question IMO is "What *protocols* does Jane have tokens for?". For example, my site speaks OpenID so which OpenID services does Jane have active sessions at (there may be many - big ones that throw in IdP services like AOL, Google, Microsoft, etc. as well as IdP-specific providers like myOpenID). If I still want to maintain a white- or blacklist of OpenID providers then that's fine, but I don't have to fire into the darkness and hope I hit something.
I'm also curious as to whether the storage of token data (rather than just returning booleans) is worth the potential cost and concerned that there might be security implications we haven't considered (e.g. sites reading/writing tokens for other domains, circumventing cookie mechanisms for tracking, interactions with SSL, etc.).