Cluster, ese es un buen frente para atacar el problema.
Como dices, la consulta se optimiza si usamos un LEFT JOIN, mas o menos así...
SELECT a.* FROM mensajes a LEFT JOIN mensajes_vistos b ON a.id=b.id_mensaje WHERE b.id_usuario=$usr and b.id is NULL
Bueno, voy a ver como me va con esta opción, muchas Gracias Cluster!
(Si alguien tiene otro punto de vista, bienvenido!)
