The message about "controlled by older version that the pdoxusrs.net" is usually a pretty clear statement that something is wrong with the locking.
Paradox creates a pair of .LCK files (Pdoxusrs and Paradox) in each directory that is being used (as tables are viewed, working directory set etc). The Paradox.lck file is for v3.5 (backward compatibility). I'm guessing that there may be a rogue Paradox.LCK lying around.
Next time all your users are out of Paradox, search for .LCK files - there should be none so if there are any, delete then. The PDoxUsrs.NET file should only exist in one place, but you've sorted that.
Hope it helps
Phil