Accounts are only as secure as the weakest identity provider
Before you decide to support identity providers who are not email providers, you should be aware that it can create a security problem for your sites. This problem is best explained by example. Lets say that Sara uses email from an E-mail provider who offers strong authentication services to their users then just regular passwords. For example, Google Mail offers two-factor authentication. If Sara logs into your site using an OpenID from her Email provider, then it is indirectly protected by that strong authentication service. What if Sara had also created an account at a social networking site that wanted to briefly try out, but she used a very weak password because she didn't plan to use the site again. If your site supports that social network as an identity provider, then a hacker can easily break into her poorly secured account at that site, and then use it to try to login to your website. The worst security problem your site can have is if it just trusts that asserted email address from the social networking site and immediately lets the hacker gain access to Sara's account on your website. So the simplest approach would be to only support email providers as identity providers.
However many websites would like to support social networks as identity providers. In that case, the best practice is to keep a list for each local account of the identity providers that can be used to gain access to the account. If an identity provider who is not on that list tries to assert the email address of that local account, then the site can prompt the user at the browser to prove ownership of the existing local account. One of the simpler ways of getting that proof is to make a note in your database of the pending account link, and then send an email to the user with a unique URL that they must click to confirm they want to approve the pending link. A more advanced version would involve redirecting the user to any of the currently listed identity providers associated with the account, however then you need to write code to handle situations where the assertion that comes back from that provider is not for the email address you are trying to link. If you want to get super fancy, you can detect the situation where the identity provider asserts an email address that does not match any existing account. In that situation your site could automatically create a new account without requiring the "proof of ownership." However if there is ever a login attempt where the identity provider is the email provider for that account, then you have to ask if they still want that other identity provider to be trusted. If you want to try to implement this support, we suggest reviewing this summary of the logic for complex IDPs.
Another challenge is whether to even allow this type of linkage for paying enterprise customers. If they want to control how their employees are authenticated, they may not be comfortable with that idea that one of their employees might have a social network account associated with their corporate email address that has been hacked, and is now being used as a backdoor into the enterprise data they are paying a SaaS vendor to host. This will especially be a concern for enterprises who run a strong authentication systems as opposed to just relying on passwords. In addition, most enterprises have a process of dealing with ex-employees that involves suspending the ability to login to their accounts, but still keeping the accounts active as opposed to deleting all the data. Enterprises will be very concerned if the ex-employee can bypasses that login suspension mechanism and still access the account.
Email address changes
In addition to the security problem above, another big challenge is that identity providers who are not email providers generally allow a user to change the email address on their account. So your website needs to be able to handle the case where an IDP account asserted frank@aol.com one day, and frank@yahoo.com the next day. One of the really nasty cases is what to do if your site already has account for both frank@aol.com and frank@yahoo.com.
Other Challenges
Some email providers also recycle usernames if the account is inactive for awhile. Their OpenID endpoints usually indicate that fact by using different URLs, or a URL suffix. However there is no clear way to detect that case if another IDP asserts that same email address.
There are additional challenges as well. The unfortunate reality is that the industry does not yet have proven best practices for how to handle this situation, but Google is part of efforts like the OpenID community to try to identity those best practices.