Columns to_id and sender_id are indexed. Id is primary key.
First of all the query uses filesort. Second - the query returns 211 rows, but checks 560 rows. In other situatuations (with different $id+$user) it may need to check thousands of rows to return a few.
I don't know, maybe it's a good idea to create multicolumn indexes on:
to_id, sender_id
and
sender_id, to_id
?
$result = mysql_query("SELECT id, subject
FROM messages WHERE
(to_id = '$id' and sender_id = '$user') or (to_id = '$user' and sender_id = '$id')
order by id DESC limit $start, $step") or die(mysql_error());
+----+-------------+-----------+-------+-----------------+-----------+---------+------+------+-----------------------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+-----------+-------+-----------------+-----------+---------+------+------+-----------------------------+
| 1 | SIMPLE | messages | range | to_id,sender_id | sender_id | 4 | NULL | 560 | Using where; Using filesort |
+----+-------------+-----------+-------+-----------------+-----------+---------+------+------+-----------------------------+
