Tal vez esto te sirva.
Para limpiar la columna.
Código:
UPDATE mensajes SET mensaje = '' WHERE mensaje LIKE 'RE:%'
Para eliminar el registro.
Código:
DELETE FROM mensajes WHERE mensaje LIKE 'RE:%'
POSDATA: Haz un respaldo de la Base de Datos antes de probar el Script.