Keys/index decision are heavily influenced by how you will query the data. I'm going to ignore insert performance, assuming that your query performance is much more important (which could be wrong assumption, only you know that). Also, based on your column names, I'm assuming message direction is important, as in within the same conversation, sometimes user X is in the messages user_from column, and sometimes is in the user_to column. In your comment to Laurence, you said you will first display a list of conversations that a user has taken part in, and then when they click on one, you will show the list of messages. So we probably aren't looking at a join, but instead a pair of queries since you will only get messages for one conversation at a time.
Query 1 will be a selection on conversations for user X, something like:
select * from conversations where user1 = X or user2 = X
At this point, both options are equivalent. Now, the second query gets the messages for a given conversation.
option 1:
select * from message where c_id = ? (c_id fetched in first query, and you associated it with each row in your listbox)
option 2:
from the listbox click, you now know you want the messages for the conversation between users X and Y:
select * from messages where (user_from = X and user_to = Y) OR (user_from = Y and user_to = X)
If all my assumptions that lead me here are correct, then clearly option 1 is superior, as it's a very fast single valued primary key lookup. Otherwise, do a similar analysis of how you will query the data, which should point to the better solution.
(as an aside, in your messages table, instead of repeating the two users, just have a 0/1 bit column indicating the direction of the conversation, since the conversation table already has an order. e.g. if conversation table has cid 1, user X, user Y, then the messages table for cid 1 can have a bit set to zero when user x is the from user, and a bit set to 1 when user y is the from user)