MySQL table not working after a few days of use
Part of the problem is that you are scanning most of 20K rows and locking the rows to be deleted as you go.  The scan, itself, is time consuming.

If you are using MyISAM, that is a big issue -- switch to InnoDB.

Don't use TIMEDIFF, it will get you in trouble for large differences.  I will assume that l.timestamp was some time in the past and that r.timeout is how many seconds before it "times out".

DELETE  l
    FROM  locking l,
          locking_rules r
    WHERE  l.origin = r.origin
      AND  r.name!='*'
      AND  l.timestamp &gt; NOW() - INTERVAL r.timeout SECOND
    LIMIT 100


And have

l: INDEX(origin, timestamp)


If the DELETE is running too slowly, either increase the frequency of running it, or increase the LIMIT.  But I would not use more than 1000.

OK, the LIMIT will probably spit at you.  So, I'll provide another possibility:

DELETE  l
    FROM  locking l,
    JOIN  ( SELECT l2.id
              FROM locking l2
              JOIN locking_rules r  ON r.origin = l.origin
                                   AND l.timestamp &gt; NOW() - INTERVAL r.timeout SECOND
              WHERE r.name!='*'
              LIMIT 100
           ) s  ON s.id = l.id;


But this will also suffer from scanning too much of locking to find the few rows that need deleting.

So, let's start over and break the task into two steps:


Find 100 ids to delete.  This is just a SELECT, so it has much less impact.
Delete those 100 (or fewer) via the PRIMARY KEY -- This is much less invasive.


thus:

CREATE TEMPORARY TABLE t
    SELECT l2.id
      FROM locking l2
      JOIN locking_rules r  ON r.origin = l.origin
                           AND l.timestamp &gt; NOW() - INTERVAL r.timeout SECOND
      WHERE r.name!='*'
      LIMIT 100;
DELETE  l, t
    WHERE l.id = t.id;


Let's prevent the various connections from doing the "same" code at the "same" time.  (In pseudo client code:)

if (GET_LOCK('messy delete) == 1)
{
    perform the above code
    RELEASE_LOCK('messy delete');
}


It may be that the sporadic hangup is due to two DELETEs stumbling over each other, perhaps even having a 'domino effect' cascading into other connections.