Peter,
Intermittant problems like this are hard to track down. If you can get to the code where the error message is generated, you could add code to gernerate an error log (INSERT INTO ErrorLog ...) where you could put potential debugging info like user, datetime, table, record number and key fields, and anything else that would be helpful.
Or better yet, if you have enough disk space, you might create a "Transaction log" with a record created each time someone logs in or out, as well as each time a user calls the save routine. Then you'd have a record of the events and transactions that led to the "Record in Use", transactions that were failing, and the events, including who logged out, that led to the system working again.
Might give you some clues into this mystery.
David.