Gremlins!
Paradox doesn't always clean up after itself, and leaves it's socks strewn on the floor. As said above, just do a search for p*.net and p*.lck (there are other net files.) and blast the suckers.
This works as well with the occasional "not enough memory" message and the the error that the program is taken by another user.
The trick is to be sure that the program is always properly ended before shutting down the computer.