Can connect but online status not updated

I am curious what would cause a user's online status to not be updated on
other clients immediately after signing in. It sometimes takes anywhere from
15 to 30 minutes before they appear online to other users. Server is
Exchange 2000 fully patched and client is Messenger 5.1. The reverse is true
when they log off. Users still appear online for several minutes after they
sign off. Is there some sort of refresh setting buried in the registry on
the server or is it a client side issue? I am currently experimenting with
the [HKEY_CURRENT_USER\Software\Microsoft\Exchange\Messenger\Profiles]
"PropertyTimeout"=dword:00000001
registry setting on a couple of machines but I have a feeling this is not
the problem.