[x-yuri]

почти догнал

mysql> SELECT u.id
    -> FROM users_2 u
    -> WHERE u.id != 5
    -> AND u.id NOT IN
    ->   (
    ->     SELECT IF(b.idu = 5, b.idb, b.idu)
    ->     FROM banned_2 b
    ->     WHERE b.idu = 5 OR b.idb = 5
    ->   )
    -> ORDER BY RAND()
    -> LIMIT 1;
+-------+
| id    |
+-------+
| 26202 |
+-------+
1 row in set (0.54 sec)

explain:

*************************** 1. row ***************************
           id: 1
  select_type: PRIMARY
        table: u
         type: range
possible_keys: PRIMARY
          key: PRIMARY
      key_len: 4
          ref: NULL
         rows: 13847
        Extra: Using where; Using index; Using temporary; Using filesort
*************************** 2. row ***************************
           id: 2
  select_type: DEPENDENT SUBQUERY
        table: b
         type: index_merge
possible_keys: PRIMARY,idb
          key: PRIMARY,idb
      key_len: 4,4
          ref: NULL
         rows: 3
        Extra: Using union(PRIMARY,idb); Using where

а у меня стоит в PRIMARY KEY добавить origin, иначе если два пользователя попытаются друг друга забанить, один из них рискует получить ошибку 1062 Duplicate entry, а то и целостность нарушится

а по поводу DEPENDENT SUBQUERY, люди даже целую хранимую процедуру написали

The real issue is that the subquery here is not really dependent on any of the columns in the outer query. The subquery will return the same result every time it is evaluated. You know that. I know that. But MySQL does not know that.