Help: Key Violation errors

I have a small database program created in Delphi Desktop 2.0 using Paradox
5.0 tables. Its running on an NT network and six win95 workstations. After
completion, it stabilized nicely for about two weeks. Now, more and more
frequently, it throws out Key Violation and Index Out of Date errors when
users try to post a new record. When this happens, all users are locked out
once they leave the application, and if they stay in the app, they can not add
new records. The only way Ive found to remedy the problem is a two step
process using Database Desktop. First I remove the five Secondary Indexes,
de-activate the Key Field, save this, then redefine everything. This takes
care of the Out of Date Indexes errors. Second, I change the Key Field from
auto-increment to a long integer, save it, then put it back to auto-increment
and let it figure out where its supposed to start counting again. This
band-aid only worked for a couple of hours the last time I tried it. Currently
there are just over 5000 records on the system. Any thoughts or ideas would be
appreciated.