If the Online Presence Indicator is not working properly on some clients it could be that the IE plugin is corrupted.

Client has Office 2003
Try reinstalling the Office Web Components.
Client has Office 2007
Try the following:
- Close all IE windows
- Rename the file C:\Program Files\Microsoft Office\Office12\name.dll to name.dll.bak (or delete it)
- Start MSN Messenger / Live Messenger / Windows Messenger (not sure why but it did the trick)
- Open a SharePoint page in IE and Office 2007 will reconfigure itself
Helped in my case !