MySQL, "columns partitioning" when multiple columns are individiually important
You are right that mysql will check only one partition for a specific sender_id, but checks all the partitions for a specific receiver_id, as shown here:

mysql&gt; explain partitions select * from messages where sender_id =5;
+----+-------------+----------+------------+------+---------------+------+---------+------+------+-------------+
| id | select_type | table    | partitions | type | possible_keys | key  | key_len | ref  | rows | Extra       |
+----+-------------+----------+------------+------+---------------+------+---------+------+------+-------------+
|  1 | SIMPLE      | messages | p0         | ALL  | NULL          | NULL | NULL    | NULL |    2 | Using where |
+----+-------------+----------+------------+------+---------------+------+---------+------+------+-------------+
1 row in set (0.00 sec)

mysql&gt; explain partitions select * from messages where receiver_id =5;
+----+-------------+----------+------------+------+---------------+------+---------+------+------+-------------+
| id | select_type | table    | partitions | type | possible_keys | key  | key_len | ref  | rows | Extra       |
+----+-------------+----------+------------+------+---------------+------+---------+------+------+-------------+
|  1 | SIMPLE      | messages | p0,p1,p3   | ALL  | NULL          | NULL | NULL    | NULL |    3 | Using where |
+----+-------------+----------+------------+------+---------------+------+---------+------+------+-------------+
1 row in set (0.00 sec)


However, there are still benefits to that partitioning, depending on your hardware.  When looking in all partitions for a receiver_id, mysql is really performing 3 select statements, one for each partition.  It may be able to parallelize these select statements.  Additionally, if you index receiver_id, it will be accessing 3, smaller, indicies.  

In the end, you just have to do performance testing and see if it is paying off for your use case.  Seeing as 100MB fits in RAM pretty easily these days, I wouldn't consider partitioning such a small table unless you have specific reasons to do so.