demo, MySQL - rextester

Language: Layout:

#MySQL 5.7.12
#please drop objects you've created at the end of the script 
#or check for their existance before creating
#'\\' is a delimiter

DROP TABLE IF EXISTS tbl_primessages;
CREATE TABLE tbl_primessages (frmid int, frnnm varchar(55), toid int, tonm varchar(55), messg varchar(255), flag int, timestamp datetime, seen int, pk int);
INSERT INTO tbl_primessages
VALUES
    (3466, 'pc', 3469, 'pc2', 'pc2',0, '2017-05-06 14:53:30', 1, 6839),
    (3466, 'pc', 3469, 'pc2', 'hiiiiii pc1', 0, '2017-05-06 14:52:57', 1, 6838),
    (3469, 'pc2', 3466, 'pc', 'hi m pc2', 0, '2017-05-06 14:40:15', 1, 6837),
    (3466, 'pc', 3469, 'pc2', 'hiiii m pc1', 0, '2017-05-06 14:36:59', 1, 6836),
    (3466, 'pc', 3467, 'mi', 'dfdfv', 0, '2017-05-04 23:30:50', 0, 6835),
    (3466, 'pc', 3467, 'mi', 'dfdfv', 0, '2017-05-04 23:18:25', 0, 6834),
    (3466, 'pc', 3467, 'mi', 'dfdfv', 0, '2017-05-04 23:18:22', 0, 6833);

SELECT t1.*
FROM tbl_primessages t1
INNER JOIN
(
    SELECT
        LEAST(frmid, toid) AS frmid,
        GREATEST(frmid, toid) AS toid,
        MAX(timestamp) AS latest_ts
    FROM tbl_primessages
    GROUP BY LEAST(frmid, toid), GREATEST(frmid, toid)
) t2
    ON LEAST(t1.frmid, t1.toid)    = t2.frmid AND
       GREATEST(t1.frmid, t1.toid) = t2.toid  AND
       t1.timestamp = t2.latest_ts;


absolute service time: 0,41 sec