Please make sure the following steps are working :
1. Verify Firewall. If you have installed Firewall (Windows XP SP2, Zone Alarm etc) in your computer, the Security Alert Warning will pop-up immediately on running Outlook Messenger. Please Unblock/Enable/Allow Outlook Messenger in the Firewall Security Alert Pop-up Warning else Outlook Messenger cannot run in the network computers.
In case, if this Security Alert Warning did not popup during installation, You can manually configure your Firewall to run Outlook Messenger.
Windows XP (SP2) Firewall
How to Configure Windows Firewall for Outlook Messenger?
Norton Antivirus 2005 Firewall
How to Configure NAV 2005 Firewall for Outlook Messenger?
MAC OS X Firewall
How to Configure MAC OS X Firewall Firewall for Outlook Messenger?
Also, please make sure the user is not filtered in your settings.
2. In Outlook Messenger Settings, Network Tab, verify Outlook Messenger is using right IP Address of your computer. If your system has multiple IP Address assigned, make sure LAN IP Address(or VPN IP Address) is selected.
3. Make sure in Network Tab, "Use Terminal Service Tool" option is not selected, If your Outlook Messenger not running as a Terminal Services Client.
4. Please make sure all users are in same LAN. If you have people in other subnets, make sure they are added in Outlook Messenger Settings, Broadcast IP / IP Range/ IP Address at BOTH ENDS. Network A computers should have added Network B IP Address in their range & viceversa. For further details Click Here
5. Verify your network and can able to PING each other. Static IPAddress recommended for all computers in the network.
But If in your network, computers used to have Dynamic IP Address(i.e Obtain an IP Address Automatically), please make sure ALL computers are having that same Dynamic IP Address option.
6. If you have already purchased Outlook Messenger, Please make sure your purchased User License not exceeds the Online Users List. For Example, if you have purchased 20 User License, only 20 users will be displayed Online.
7. It is recommended to use same outlook messenger version for all users in network.