Ok so I didn't commit the db transaction after unlink(). That solved my problem.

For reference here's what I did in the odoo.sh shell

odoo-bin shell
env['mail.message'].with_user(8)._message_fetch(domain=[('needaction', '=', True)])  # to replicate the error and find the offending message id's
env['mail.message'].with_user(8).search([('needaction', '=', True), ('res_id', '=', 51)]).sudo().unlink()
self.env.cr.commit()