Yo lo que no entiendo,
@melado, es por qué el listado de mensajes de un usuario es algo público. No debería ser así, dar una herramienta de búsqueda a terceros (que, además, termina creando problemas).
Y no, no sirve de nada darse de baja, porque cuando un usuario se da de baja y te metes en su perfil, aunque no te muestra nada sí sale la ID del usuario en la barra de direcciones. Con lo que metiéndote en tu propio perfil y dándole a buscar tus propios mensajes, cambias la ID tuya por la del usuario dado de baja y... voilá
A ese tema le tenéis que dar muchas vueltas. Una solución que te propongo y que debería ser fácil es la de quitar la ID de la barra de direcciones cuando un usuario ha dejado inactiva su cuenta, para que no hagan lo que te he dicho. Por ejemplo enlazando a una página única que avise de que ese usuario está dado de baja, y que sea la misma página para todos. Así no muestra información como la del ID
Otra, y que en mi opinión debería ser así, es que el motor de búsqueda de mensajes sea para el propio usuario, no para todos.