[x-yuri]

а теперь давайте сравним
создание таблиц:

-- users_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);

-- banned_2
drop table if exists banned_2;
create table banned_2 (
    idu int,
    idb int,
    primary key(idu, idb)
);
insert into banned_2 values
(2, 3),
(1, 3),
(3, 4),
(3, 5);

-- banned_3
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');

explain:

EXPLAIN
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;
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: u
         type: index
possible_keys: NULL
          key: PRIMARY
      key_len: 4
          ref: NULL
         rows: 6
        Extra: Using index; Using temporary; Using filesort
*************************** 2. row ***************************
           id: 1
  select_type: SIMPLE
        table: f
         type: eq_ref
possible_keys: PRIMARY
          key: PRIMARY
      key_len: 8
          ref: u.id,const
         rows: 1
        Extra: Using where; Using index; Not exists

EXPLAIN
SELECT u.id
FROM users_2 u
WHERE u.id != 3
AND u.id NOT IN
  (
    SELECT IF(b.idu = 3, b.idb, b.idu)
    FROM banned_2 b
    WHERE b.idu = 3 OR b.idb = 3
  )
ORDER BY RAND()
LIMIT 1;
*************************** 1. row ***************************
           id: 1
  select_type: PRIMARY
        table: u
         type: index
possible_keys: PRIMARY
          key: PRIMARY
      key_len: 4
          ref: NULL
         rows: 6
        Extra: Using where; Using index; Using temporary; Using filesort
*************************** 2. row ***************************
           id: 2
  select_type: DEPENDENT SUBQUERY
        table: b
         type: index
possible_keys: PRIMARY
          key: PRIMARY
      key_len: 8
          ref: NULL
         rows: 3
        Extra: Using where; Using index

EXPLAIN
SELECT id 
FROM users_2 U 
WHERE 
  ISNULL((SELECT id 
    FROM banned_2 
    WHERE idu=3 && idb=U.id || idb=3 && idu=U.id
    ))
ORDER BY RAND()
LIMIT 1;
*************************** 1. row ***************************
           id: 1
  select_type: PRIMARY
        table: U
         type: index
possible_keys: NULL
          key: PRIMARY
      key_len: 4
          ref: NULL
         rows: 6
        Extra: Using where; Using index; Using temporary; Using filesort
*************************** 2. row ***************************
           id: 2
  select_type: DEPENDENT SUBQUERY
        table: banned_2
         type: index
possible_keys: PRIMARY
          key: PRIMARY
      key_len: 8
          ref: NULL
         rows: 3
        Extra: Using where; Using index

EXPLAIN
SELECT u.id, b.idu , b.idb
FROM users_2 u
LEFT JOIN banned_2 b
ON ((b.idu = 3 OR b.idb = 3) AND (u.id = b.idu OR u.id = b.idb))
WHERE ( (b.idu IS NULL) AND (b.idb IS NULL))
ORDER BY RAND()
LIMIT 1;
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: u
         type: index
possible_keys: NULL
          key: PRIMARY
      key_len: 4
          ref: NULL
         rows: 6
        Extra: Using index; Using temporary; Using filesort
*************************** 2. row ***************************
           id: 1
  select_type: SIMPLE
        table: b
         type: index
possible_keys: PRIMARY
          key: PRIMARY
      key_len: 8
          ref: NULL
         rows: 3
        Extra: Using where; Using index; Not exists

запуск на более-менее реальных данных:

mysql> SELECT u.*
    -> FROM users_2 u
    ->     LEFT JOIN filters_2 f ON u.id = f.user_1_id && f.user_2_id = 5
    -> WHERE f.user_1_id IS NULL && u.id != 5
    -> ORDER BY RAND()
    -> LIMIT 1;
+------+
| id   |
+------+
| 6569 |
+------+
1 row in set (0.28 sec)

mysql> SELECT u.id
    -> FROM users u
    -> WHERE u.id != 5
    -> AND u.id NOT IN
    ->   (
    ->     SELECT IF(b.idu = 5, b.idb, b.idu)
    ->     FROM banned b
    ->     WHERE b.idu = 5 OR b.idb = 5
    ->   )
    -> ORDER BY RAND()
    -> LIMIT 1;
+-------+
| id    |
+-------+
| 25324 |
+-------+
1 row in set (1 min 56.50 sec)

mysql> SELECT id
    -> FROM users_2 U
    -> WHERE
    ->   ISNULL((SELECT id
    ->     FROM banned_2
    ->     WHERE idu=5 && idb=U.id || idb=5 && idu=U.id
    ->     ))
    -> ORDER BY RAND()
    -> LIMIT 1;
+------+
| id   |
+------+
| 5419 |
+------+
1 row in set (1 min 56.53 sec)

mysql> SELECT u.id, b.idu , b.idb
    -> FROM users_2 u
    -> LEFT JOIN banned b
    -> ON ((b.idu = 5 OR b.idb = 5) AND (u.id = b.idu OR u.id = b.idb))
    -> WHERE ( (b.idu IS NULL) AND (b.idb IS NULL))
    -> ORDER BY RAND()
    -> LIMIT 1;
+------+------+------+
| id   | idu  | idb  |
+------+------+------+
| 9609 | NULL | NULL |
+------+------+------+
1 row in set (2 min 1.47 sec)