Query data via username - pair - best performance
Critique
1A cannot use indexes because of OR
1B -- user_1 = '%' prevents the use of INDEX(user_1, ...), so solution 1B is out.
1B can be salvaged by having a second index:  INDEX(user_2).  Then simply say
SELECT * FROM my_table WHERE user_1 = name_1
UNION ALL
SELECT * FROM my_table WHERE user_2 = name_1;

2-- FULLTEXT has limitations, such as &quot;word&quot; length.  So be cautious.
2A  (WHERE MATCH(users) AGAINST ('&quot;name_1-name_2&quot;,&quot;name_2-name_1&quot;') -- it is probably sufficient to say simply
WHERE MATCH(users) AGAINST ('+name_1 +name_2' IN BOOLEAN MODE); The +` says that both are required, but in any order.
2B -- OK (with the above caveats)
FULLTEXT, when it is applicable, is likely to be very performant.  Here are two tricks I have used:
WHERE MATCH(text) AGAINST(&quot;R +James&quot; IN BOOLEAN MODE)

The short 'word' (R) will be ignored; it will search for James efficiently.  Note the selective use of '+'.
WHERE MATCH(text) AGAINST(&quot;R +Anders&quot; IN BOOLEAN MODE)
  AND user LIKE &quot;%R. Anders%&quot;

This assumes that the name might be in the middle of a large column, and I need to check the initial.  The FT test will be first (and fast), followed by the LIKE (slow, but against few rows).
That still has problems because of &quot;E. Anders and R. Anderson&quot; would be wrongly caught.
(Etc, etc.  But I digress from your simple 2-word use case.)
Bottom line:
1B (extra index) is optimal.  (But I suspect you watered down the Question.)
FULLTEXT would be my next choice.
Let me add an option 3:
Sort the users before inserting and when querying.  That is
INSERT ... (user1, user2)
   VALUES
   (LEAST(?, ?), GREATEST(?, ?))

then you need (for case A) only INDEX(user1, user2) together with
WHERE user1 = LEAST(?, ?)
  AND user1 = GREATEST(?, ?)

Alas, that will probably mess up case B.  (Do all rows have 2 user names, but some queries have only 1 user?)
And Option 4
Have another table that maps user names to my_table by id.  Typically 2 rows in this new table for each row in my_table.  Optionally toss the user columns from my_table.
I won't go into the rest of the detail; they do get messy.