- I would add an index on users_roles `(rid, uid)`. In a many-to-many table with two columns `(a,b)`, you almost always will need both indexes: `(a,b)` and `(b,a)` in one query or the other. I think this index would help in this query.

- Try various rewritings of the query and the `EXPLAIN EXTENDED` they produce.

- About your suggestions, the first is not correct (it will not show same results). For the second suggestion:

.

    WHERE users.status = 1                                           -- Active users only

Yes, that's better than `users.status <> 0`. This change may have a better effect if there is an index on `users (status)` (and even more if there are not many active users). Optimizing queries with boolean columns (or ones that act as boolean) is not easy with B-trees.

      AND users.uid IN
         (SELECT DISTINCT uid FROM users_roles WHERE rid = 5)        -- Must be in rôle A

No. MySQL is known to have issues with `column IN (SELECT ...)`, especially if the external table is big (and yours is 200K columns, so no, not good).

      AND users.uid NOT IN
         (SELECT DISTINCT uid FROM users_roles WHERE rid IN (6,8,9)) -- Not rôles B, C, D

Yes, that is one way to rewrite. The `DISTINCT` is redundant though.

      AND users.uid <> :users_uid                                    -- Not current user

Yes, removing the `users.uid IS NOT NULL` may help and does not change the result.

- Other things you could try:

Moving the `rid = 5` condition to the `ON` clause:

    INNER JOIN users_roles users_roles 
      ON  users.uid = users_roles.uid
      AND users_roles.rid = 5

The (rewrite) to `NOT IN` can also be written with `NOT EXISTS`:

      AND NOT EXISTS 
          ( SELECT * 
            FROM users_roles ur 
            WHERE ur.rid = users.uid 
              AND ur.rid IN (6,8,9)
          )