Making a message system
Your primary key is fine. I don't see a reason to change it.

The issue you are having is because you are basing your query on the messsage_id and it being without gaps. You could base your queries on the message_time column (I suppose this holds the datetime that the message was sent). 

Even if you keep using the messsage_id for the queries (assuming that biggest id means the latest message - which may not always be correct), you can still write a query that returns always 20 messages, gaps or not - just change ORDER BY message_time DESC to ORDER BY messsage_id DESC in the 3 places it appears:

SELECT *
FROM
  (   ( SELECT message_id, message_time,
               'U &lt;- F' AS direction
               message_read, message_body
        FROM member_messages AS msg
        WHERE message_to = :userId
          AND message_from = :friendId
     --   AND message_deleted = 0
        ORDER BY message_time DESC
            LIMIT 20 
      )
    UNION ALL
      ( SELECT message_id, message_time,
               'U -&gt; F' AS direction
               message_read, message_body
        FROM member_messages AS msg
        WHERE message_to = :friendId
          AND message_from = :userId
          AND message_deleted = 0
        ORDER BY message_time DESC
            LIMIT 20 
      )
    ORDER BY message_time DESC
        LIMIT 20 
  ) AS tmp 
ORDER BY message_time ASC;


Other issues:

You probably meant to have the deleted = 0 check on both cases (message sent by me to friend and sent by friend to me). If yes, undelete the commented line above - and note that AND has higher precedence than OR in SQL. The condition you probably wanted to use was (note the removed pair of parenthesis):

WHERE (    MSG.message_to = :userId
       AND MSG.message_from = :friendId
      OR 
           MSG.message_to = :friendId
       AND MSG.message_from = :userId
      )
  AND ...


So, you could write the query like this:

SELECT *
FROM member_messages AS msg
WHERE (    MSG.message_to = :userId
       AND MSG.message_from = :friendId
      OR 
           MSG.message_to = :friendId
       AND MSG.message_from = :userId
      )
      AND message_deleted = 0
ORDER BY message_time DESC
    LIMIT 20 ;


I used UNION for efficiency reasons. Complicated conditions with OR may not be optimized very well. You could also add an index on (deleted, message_from, message_to, message_time).