At first I thought it would be an easy problem of the master and slaves being out of sync and the row-based replication failing on not finding the row, but then I noticed all machines were actually still running statement-based replication. As far as I could recall we did that to circumvent another issue that has already been solved months ago but for some reason we never put it back to row-based replication.
A simple SHOW SLAVE STATUS revealed something similar to this:
Last_Error: Error 'Duplicate entry '272369' for key 'PRIMARY'' on query. Default database: 'userdata'. Query: 'DELETE u, uf1, uf2, up FROM `users` u LEFT JOIN `friends` uf1 ON u.id = uf1.id LEFT JOIN `friends` uf2 ON u.id = uf2.friend_id LEFT JOIN `prefs` up ON u.id = up.id WHERE u.name = 'testuser';