My group also is fighting this problem using Access 2000 on a network with Windows 2000. We never had the problem with NT 4.0 (used it for 4 years) but is a real problem with Windows 2000, started almost the day we converted. Many times someone using Access has a PC problem that causes an illegal shut down or an uncontrolled exit to Access and this sets a flag that the data in the tables might be corrupt. They usually never are, but you have to compact and repair the database to reset that flag.
We have had many network problems that affect our 'link' the the server where Access is stored, thus causing the corrupt message. Many times when our db's go corrupt, we can associate the problem to a network error/problem, illegal shutdown, etc. Try to see if there is one particular PC that is having hardware problems on other applications that is causing that person to just do a warm boot on his/her PC without exiting ACCESS first.
Or if it happens at a certain time of the day.
Also, if you're using linked tables, try putting the application itself on each person's individual drive - not a shared folder. That way, if one goes corrupt, the others won't be affected. It might also help point to the PC that might be having hardward problems affecting Access. (Assuming of course, that is not the table database that is going corrupt.
Good luck.