NT4.0 Server Logon Problem (Hard One)

During the suddenly users can not logon to the Domain. When you go to Server, Users Sessions, in the control panel, on e users is loged on any were from three to hundreds of times in the connected users, thus all of the licenses al taken and noo more are available. If you disconnect the user and have him reboot his computer, most of the time everything is returned to normal. Our Anti-Virus is up to date on all computers in the network and a complete scan is run daily. No new software has been added to the Severs, and last night I downloaded and reinstalled Service Pack 6a. The problem reoccurred again this morning. Any solutions or suggestions, short of reinstalling Nt server would be greatly appreachiated.