AFAIK, there is no way to use the Exchange SDK to determine which mailboxes
are currently logged into (even though you can see last login times with
Exchange System Manager).  Perhaps you can use WMI to read this data, I'm not
sure - don't know much about WMI.

From the client side, you could write a VBA macro or COM Add-In to log
application startup/shutdowns, but you would need to do this on every PC
running Outlook.

Other alternatives could be to integrate with Windows Messenger to read
presence status:

Windows Messenger:
http://msdn.microsoft.com/library/en-us/WinMessenger/winmessenger/messenger_entr
y.asp?frame=true

Or build your own messenger app to do this:

Enhancing Rich Client Communications with the Microsoft Real-Time
Communications API (Windows XP Technical Articles):
http://msdn.microsoft.com/library/en-us/dnwxp/html/rtc_enhancerichclient-real-ti
mecomm.asp?frame=true

Anyway, if detecting online presence is not a priority, you can still search
the GAL for a specific business telephone number, but you need to use CDO.  
Here's an example that loops through the entire GAL looking for a user's full
name.  You can easily change it to look for the phone number:

Sub GetGALAddressDetails(UserFullName As String)
On Error Resume Next

   Dim objSession As New MAPI.Session
   Dim objAdds As MAPI.AddressLists
   Dim objAddress As MAPI.AddressEntry
   Dim objGAL As MAPI.AddressList
   Dim objFields As MAPI.Fields, objField As MAPI.Field
   
   objSession.Logon , , , False
   
   If objSession Is Nothing Then Exit Sub
   
   Set objAdds = objSession.AddressLists
   Set objGAL = objAdds.Item("Global Address List")
   For Each objAddress In objGAL.AddressEntries
       If objAddress.DisplayType = CdoUser Or objAddress.DisplayType =
CdoRemoteUser Then
           If InStr(objAddress.Name, UserFullName) > 0 Then
               Set objField = objAddress.Fields(CdoPR_BUSINESS_ADDRESS_CITY)
               If Not objField Is Nothing Then Debug.Print objField.Value:
Set objField = Nothing
               Set objField =
objAddress.Fields(CdoPR_BUSINESS_ADDRESS_COUNTRY)
               If Not objField Is Nothing Then Debug.Print objField.Value:
Set objField = Nothing
               Set objField =
objAddress.Fields(CdoPR_BUSINESS_ADDRESS_POSTAL_CODE)
               If Not objField Is Nothing Then Debug.Print objField.Value:
Set objField = Nothing
               Set objField =
objAddress.Fields(CdoPR_BUSINESS_ADDRESS_STATE_OR_PROVINCE)
               If Not objField Is Nothing Then Debug.Print objField.Value:
Set objField = Nothing
               Set objField =
objAddress.Fields(CdoPR_BUSINESS_ADDRESS_STREET)
               If Not objField Is Nothing Then Debug.Print objField.Value:
Set objField = Nothing
               Set objField = objAddress.Fields(CdoPR_TITLE)
               If Not objField Is Nothing Then Debug.Print objField.Value:
Set objField = Nothing
               Set objField = objAddress.Fields(CdoPR_COMPANY_NAME)
               If Not objField Is Nothing Then Debug.Print objField.Value:
Set objField = Nothing
               Set objField = objAddress.Fields(CdoPR_DEPARTMENT_NAME)
               If Not objField Is Nothing Then Debug.Print objField.Value:
Set objField = Nothing
               Set objField = objAddress.Fields(CdoPR_OFFICE_LOCATION)
               If Not objField Is Nothing Then Debug.Print objField.Value:
Set objField = Nothing
               Set objField = objAddress.Fields(CdoPR_ASSISTANT)
               If Not objField Is Nothing Then Debug.Print objField.Value:
Set objField = Nothing
               Set objField =
objAddress.Fields(CdoPR_BUSINESS_TELEPHONE_NUMBER)
               If Not objField Is Nothing Then Debug.Print objField.Value:
Set objField = Nothing
           End If
       End If
   Next
   
   objSession.Logoff
   
   Set objSession = Nothing
   Set objAdds = Nothing
   Set objAddress = Nothing
   Set objGAL = Nothing
   Set objFields = Nothing
   Set objField = Nothing
End Sub