Non ho guardato molto bene la tabella MA la prima idea che mi viene in mente e' di dividere in due la tabella: in una tieni i messaggi piu' vecchi di 1, 2, 3 mesi a tua scelta (questi messaggi vengono consultati rarissimamente). In un'altra tieni i messaggi sufficientemente recenti.

Piu' tardi do' un occhio approfondito anche allo schema, ma in ogni caso mi sembra che a naso tu abbia un po' troppi indici.