В итоге, я добавил суррогатный PK, вместо 3-х составных полей. Если не учитывать денормализацию БД, считаю это оптимальным решением. Итоговый запрос:

SELECT U.*, S.*
FROM `user` AS U
LEFT JOIN stats AS S 
  ON S.id = (
    SELECT id
    FROM stats AS S2 
    WHERE S2.user_id = U.id
    ORDER BY id DESC
    LIMIT 1
  )

Я получаю необходиммые мне данные — все поля последней записи таблицы stats с любым типом (можно указать конкретный тип) для каждого юзера. При этом сортировка по ID будет быстрее, чем по дате. Запись для JOIN'а теперь однозначная, ситуация выборкой нескольких записей статсы с одинаковой датой решена.
Осталось прогнать на более-менее реальном наборе данных и оценить производительность.
Всем спасибо за помощь.