Problems with NIS SuSE 8.0

Hello list! I set up a network of 4 Clients with NIS + NFS connected to one server. So far everything works fine since ~ 3/4 year. But sometimes it happens that if you login, every password is accepted or none. Which means that you can login with any account and no password verification. The NIS Server is running with SuSE 8.0 and all patches installed. Clients are running SuSE 7.3 and 8.1, both versions show the same behaviour. Has anybody seen this behaviour and a solution for it. Thanks for hints and tips, Harald Steden