I am updating this topic to ensure that you never come here for information that is located elsewhere. The KB should always be authoritative, what you find here would be a supplement or clarification.
I will post here the summary of main presence related issues so you get an idea of what you might need to consider.
 
Non KB but common issue
The SIP-URI and Email alias differ. Make them the same or add each alias to Sharepoint. Known issue with no current fix, only the workarounds.
 
Available KB Articles for Presence
Windows Sharepoint Services does not display the correct presence information of a Windows Messenger contact (889938) http://support.microsoft.com/default.aspx?scid=kb;en-us;889938
The key to this article is a registry key
To modify this behavior, change the QueryServiceForStatus value in the following registry subkey:
HKEY_CURRENT_USER\Software\Microsoft\Office\11.0\Common\PersonaMenu
To do this, follow these steps:
1. Click Start, click Run, type regedit, and then click OK.
2. Locate and then click the following registry subkey:
HKEY_CURRENT_USER\Software\Microsoft\Office\11.0\Common\PersonaMenu
If this registry subkey does not exist, create it. To do this, follow these steps:
a. Right-click Common, point to New, and then click Key.
b. In the New Key # 1 box, type PersonaMenu, and then press ENTER.
3. Right-click PersonaMenu, point to New, and then click DWORD Value.
4. In the New Value # 1 box, type QueryServiceForStatus, and then press ENTER.
5. Right-click QueryServiceForStatus, and then click Modify.
6. In the Value data box, type one of the following values:
• 0
If you type a value of zero, you receive status information only about people who are on your contact list. In this scenario, Outlook does not request status information about people who are not on your contact list.
• 1
If you type a value of one, Outlook requests status information from the Microsoft Exchange Instant Messaging (IM) service about people who may or may not be on your contact list.
• 2
If you type a value of two, Outlook requests status information from the Real-Time Communications (RTC) service about people who may or may not be on your contact list.
7. Click OK, and then quit Registry Editor.
 
 
834471 A Live Communications Server user's presence information does not appear http://support.microsoft.com/?id=834471