This is a standard problem.
Note that MySQL allows you to omit columns from the GROUP BY clause, which Standard SQL does not, but you do not get deterministic results in general when you use the MySQL facility.
SELECT *
FROM Messages AS M
JOIN (SELECT To_ID, From_ID, MAX(TimeStamp) AS Most_Recent
FROM Messages
WHERE To_ID = 12345678
GROUP BY From_ID
) AS R
ON R.To_ID = M.To_ID AND R.From_ID = M.From_ID AND R.Most_Recent = M.TimeStamp
WHERE M.To_ID = 12345678
I've added a filter on the To_ID
to match what you're likely to have. The query will work without it, but will return a lot more data in general. The condition should not need to be stated in both the nested query and the outer query (the optimizer should push the condition down automatically), but it can do no harm to repeat the condition as shown.