If you are using Pdox for DOS, Tutility is a separate program you will find in the same directory where you have installed Pdox. This program will fix corrupted tables.
If you are using Pdox for Windows, you will find it in one of the drop down menu, Table Repair.
Let's try this, kick or when all users are off Paradox, do a search for all *.lck and *net files. If there are any, delete them all.
I believe it's locking problem. Since this have been going on for 2 years, I am afraid you might have bigger problem. :-( Each time you exit Pdox abnormally, you run the risk of corrupting the tables.
Here is a test I used to use in Novell.
Create a test table on the network.
On one workstation (A), open the table.
Logon to another workstation (B).
Open the same table.
If successfull, put it in edit mode, add a record.
Put in some dummy values. Save it.
Go to workstation A, see if the record shows up.
If yes, try edit the record.
Basically, you are testing the locking of the table under a control environment. If you have encountered no problems. Then, your Pdox is set up correctly.
If not, then, you could have corrupted tables or your Pdox was never set up correctly.
You may want to consider getting some professional help.
Good Luck.