MySQL query randomly hangs on 'sending data' status?

Wow, thanks to Masood Alam's comment I found and solved the problem.

Using SHOW ENGINE INNODB STATUS turns out to be very helpful in debugging.

It turns out that with some values for user_id the database handles things differently, hence its unpredictable behaviour and not being able to reproduce the problem. Through the status command I was able to copy and paste the exact query that was running at the moment.

This are the results of EXPLAIN of that particular value for user_id:

Id | select_type | table | type         | possible_keys        | key          | key_len | ref  | rows | Extra
 1 | SIMPLE      | a     | ALL          | NULL                 | NULL         | NULL    | NULL |  841 | 
 1 | SIMPLE      | b     | index_merge  | user_id,year,test_id | user_id,year | 4,4     | NULL |   13 | Using intersect(user_id,year); Using where

A follow-up question would be now be how this behaviour can be explained. However, to fix the problem for me was just to change the query to:

SELECT a.prefix, a.test_id, a.method_id, b.test_id
FROM a
LEFT JOIN b ON b.test_id = a.test_id
WHERE
b.id IS NULL
OR user_id = ?
AND year = ?

Of which EXPLAIN results in:

Id | select_type | table | type | possible_keys | key     | key_len | ref          | rows | Extra
 1 | SIMPLE      | a     | ALL  | NULL          | NULL    | NULL    | NULL         |  671 | 
 1 | SIMPLE      | b     | ref  | test_id       | test_id | 4       | db.a.test_id |   49 | Using where

Now I know, that InnoDB can have different approaches for executing queries given different input values. Why? I still don't know.