What is locking order of MySQL on query with join statement
It is quite natural for the Optimizer might pick different query plans for those two queries.  Even if the EXPLAINs look similar today, they could be different tomorrow.

Regardless, you should plan on deadlocks; it is often futile to try to eliminate all of them.  When you get a deadlock, replay the entire transaction; it is very likely to succeed the second time.

Yes, there can be edge cases where two "independent" queries can collide.  This is probably because of edge cases where gap locking collided - or something like that.

There might be cryptic clues in SHOW ENGINE INNODB STATUS;

This index on user might decrease the frequency of deadlocks:

INDEX(status, age)


And it is likely to speed up the queries when you have a lot of rows.