мой вариант:
в двух словах:
идея заключается в том, чтобы помещать в таблицу банов 2 строки на каждую связь (два направления), тогда
drop table if exists users_2;
create table users_2 ( id int primary key );
insert into users_2 values (1), (2), (3), (4), (5), (6);
drop table if exists banned_3;
create table banned_3 (
user_1_id int,
user_2_id int,
origin enum('1', '2'),
primary key(user_1_id, user_2_id)
);
insert into banned_3 values
(2, 3, '1'), (3, 2, '2'),
(1, 3, '1'), (3, 1, '2'),
(3, 4, '1'), (4, 3, '2'),
(3, 5, '1'), (5, 3, '2');
SELECT u.*
FROM users_2 u
LEFT JOIN banned_3 f ON u.id = f.user_1_id && f.user_2_id = 3
WHERE f.user_1_id IS NULL && u.id != 3
ORDER BY RAND()
LIMIT 1;