Does the user have more than one community in his client? If he has and for example users firstname.lastname@example.org and email@example.com both of which resolve to the same Community server then this can produce this result.
When he logs into firstname.lastname@example.org he seems User A listed and on line but also sees User A listed but not on line. This is because they are separate users from separate Communities.
Have the user export their buddy list and look for yourself.
You should also see more than one community listed.
The bit that doesn't make sense is that after he "manually refreshes" it the users show correctly. What does he do to manually refresh it?
Can you close the client and rename the workspace directory and have him log in. Does it happen still?
You could back up his buddy list as the screen shot above shows and then have him log out and then delete his documents from vpuserinfo.nsf. Then he can log in and then import his contacts again assuming there isnt a second community server listed.
If there is a second community server, then just delete it after backing up the buddy list to xml.