I ran into an issue today where Outlook 2010 would not display presence from Microsoft Lync. The customer had un-installed Outlook 2010 and re-installed and that did not fix it. We also had the customer remove Lync 2010 and delete the local cache. That did not fix it either. I went into the registry and looked under HKEY_LOCAL_MACHINE\SOFTWARE\Wow6432Node\IM Providers and saw 2 entries (see image below). The problem was the ConnectMessenger key. I exported that key just in case I needed it again and then I deleted the key. After restarting Outlook 2010 presence started to work again. ConnectMessenger is part of the WebEx connect software. Apparently there is some sort of problem with the 2 programs running on the same PC.
The registry key for 32-bit systems would be HKEY_LOCAL_MACHINE\SOFTWARE\IM Providers
Update 6/13/13: This issue is also directly related to the following registry key:
You need to edit the “DefaultIMApp” value to reflect “Lync” without quotes. Once this is done exit Outlook and then open. Presence will now work.