Making a message system I have created a messaging system with MySQL structure is as follows
      `message_id` int(11) NOT NULL AUTO_INCREMENT,
      `message_from` int(11) NOT NULL,
      `message_to` int(11) NOT NULL,
      `message_body` varchar(255) NOT NULL,
      `message_time` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP,
      `message_deleted` tinyint(1) NOT NULL DEFAULT '0',
      `message_read` tinyint(1) NOT NULL DEFAULT '0',
      PRIMARY KEY (`message_id`),
      KEY `message_from` (`message_from`),
      KEY `message_to` (`message_to`)

Currently The PK is an AUTO_INCREMENT so I am wondering if using this kind of key will be efficient for this type of system. Also the main reason why i am having a asking this question is to help in my function I have been having some issues with loading more messages. due to the fact that messages are deleted the PKs will not be consistent such as 1,2,3,10,255,300. When I try to run the more function using
(SELECT MAX(message_id)
 FROM member_messages 
 WHERE (message_to = :userId
 AND message_from = :friendId)
 OR  
 (message_to = :friendId
 AND message_from = :userId))AS max_id,
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 MSG.message_deleted = '0'
HAVING MSG.message_id &gt;= max_id - 20
AND MSG.message_id &lt;= :upperId 
ORDER BY message_id ASC

In effect this query should return messages from the last 20 entered, but due to the PK being inconsistent sometimes no messages are returned. Eg. if the max_id is 200, 200- 20 is 180 and the messages with ID between this range are deleted or not associated with this members(userId) recipient(friendId). Any insight into this problem as to whether I should change the key type or change the query itself? Thanks for your time.
EDIT
Just a side note I used ASC because I wanted the newest messages to appear at the bottom of the DIV, while the fetched results would be older and appear at the top.
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).