1.)
SELECT *
FROM private_messages a
WHERE (a.from = $my_id AND a.to = $other_id) OR
(a.from = $other_id AND a.to = $my_id)
ORDER BY stamp DESC
2.)
SELECT f.*
FROM
(
SELECT *
FROM private_messages a
WHERE (LEAST(a.from, a.to), GREATEST(a.from, a.to), a.stamp)
IN (
SELECT LEAST(b.from, b.to) AS x,
GREATEST(b.from, b.to) AS y,
MAX(b.stamp) AS msg_time
FROM private_messages b
GROUP BY x, y
)
) f
WHERE $my_id IN (f.from, f.to)
ORDER BY f.stamp DESC