Access - Pérdida de Llave Primaria

Hola a todos.
Tengo el siguiente problema.
Tengo una base de datos que esta compartida en una red, a esta base de datos acceden de forma simultanea dos usuarios en dos máquinas distintas.

Hay una tabla a la que ellos acceden constantemente, agregan, borrar, actualizan de manera simultanea y constante, en algunos momentos la tabla pierde la llave primaria y tengo que estar recreando la llave primaria, por supuesto al perder la llave primaria pierde las relaciones hacia otras tablas.

Espero que alguien me ayude.
Saludos.

Se me olvido decir que la base de datos esta en Access 2000, con todas la dichosas actualizaciones de Access y con el Service Pack 7.0 del Microsoft Jet 4.0

Saludos.