Причем здесь PHP совершенно мне не ясно. Как вы храните данные конечно вы не скажите, потому мой хрустальный шар подсказал что в базе данных (если это не так начните с того что бы хранить все в БД).
SLECT DISTINCT user.id, user.name FROM user
LEFT JOIN message ON user.id = message.user_id
WHERE messages.target_user = $user_id$ OR messages.user_id = $user_id$
-- $user_id$ это для какого юзера ищем список контактов
-- messages.target_user - id юзера которому предназначается сообщение
-- messages.user_id - id отправителя
ну вот примерно таким запросом можно найти всех пользователей которым мы писали или которые нам писали.
