Retrieving most recent X rows for each given user from a table
I hope you are willing to do some programming outside of SQL.

To find the recipients that need the most pruning:

SELECT recipient
    FROM inbox
    GROUP BY recipient
    HAVING COUNT(*) &gt; 30
    ORDER BY COUNT(*) DESC
    LIMIT 100


Then, for each recipient, first find the 31st id:

SELECT id
    FROM inbox
    WHERE recipient = $recipient
    ORDER BY id DESC
    LIMIT 30,1


And delete the excess baggage:

DELETE FROM inbox
    WHERE recipient = $recipient
      AND id &lt; $id


You would need INDEX(recipient, id).

This process could be running continually.  The first SQL would be the slowest, but it would run "Using index" and probably not be too bad, maybe 0.1 sec for 200K rows in inbox.

If you want to stay in SQL, this would let you do one recipient at a time:

BEGIN;
SELECT @recipient := recipient
    FROM inbox
    GROUP BY recipient
    HAVING COUNT(*) &gt; 30
    ORDER BY COUNT(*) DESC
    LIMIT 1
    FOR UPDATE;
SELECT @id := id
    FROM inbox
    WHERE recipient = @recipient
    ORDER BY id DESC
    LIMIT 30,1
    FOR UPDATE;
DELETE FROM inbox
    WHERE recipient = @recipient
      AND id &lt; @id;
COMMIT;


Then, put that in a Stored Procedure with a loop around it.  And, if you want to be further 'nice', add a SELECT SLEEP(1); in the loop but outside the transaction.

(Trying to do the entire thing in a single statement makes my brain hurt.)