Публикую нагугленный вариант ответа.
Скорость запроса конечно с 0.042 упала до 0.115 (все пока что без индексов), но все же - это выход.
SELECT * FROM (SELECT * FROM message WHERE device_id=12 ORDER BY date DESC) AS msg WHERE device_id=12 GROUP BY thread_id ORDER BY date DESC LIMIT 0 , 50
