To help you troubleshoot this, here is a very important piece of information to keep in mind:
Locks, in MySQL, whether they are on rows, tables, advisory/named locks, and even the global FLUSH TABLES WITH READ LOCK are held by continued existence of the specific connection thread that obtained the lock. When I say "connection thread," in this context, I mean the specific instance of a client's connection to the server... the one where the lock was requested. These are the threads listed in SHOW FULL PROCESSLIST;
If the requesting connection is closed gracefully, all locks requested by that connection release immediately.
If the specific connection thread is killed by an admin (mysql> KILL #; where # is the ID from SHOW FULL PROCESSLIST that you want to force to disconnect) the locks are released as soon as that thread disappears from SHOW FULL PROCESLIST;
If that connection is not closed gracefully, the connection eventually times out (the default is 28800 seconds unless you have changed it) and then the locks are released.
Row and table locks cannot persist in the absence of the connection that originally obtained the lock... so there is no such thing in MySQL as locks piling up over time and needing to be unlocked, in the absence of client connections still holding on to the locks.
Even if it's the case that clients are improperly holding locks, then forcing a disconnect of the client will be your only workaround, as locks are there for a reason... to keep your data consistent. Forcing disconnect does not mean having everyone log out, since you've explain this isn't practical. See the KILL command, above.
My speculation is that Access is not properly interpreting responses from MySQL and only thinks records are locked when in fact it's something else.
As has already been observed, you should be able to update values in these rows using Toad, HeidiSQL, Query Browser, Workbench, or simply the mysql command line... and it's very likely you will be able to update them no problem... proving that they aren't really locked, and that Access is just confused.
Posting the precise wording of the message users are seeing from Access will probably be the best way to shed accurate light on the problem.