If I query records matching some value, why does InnoDB examine most of the records that had that value once, but have changed since then?
DESCRIBE, alias EXPLAIN, estimates the number of rows.  In your case (frequent changing of status and deletion), the number are very likely to be very far off.  Do not trust it.

EXPLAIN gets its information from "statistics" about the distribution of the data in the table.  The statistics are updated at certain times.  Version 5.7 does the update at quite different times than 5.5.  (What version are you running?)

You have INDEX(status)?  Perhaps you should not; it is adding to the problem and not helping the solution in a consistent way.  How often are the status changes?  The DELETEs?  There may be workarounds.

The Optimizer will look at the statistics for status and incorrectly decided that status=0 was too common for using the INDEX, so it did a table scan instead.  On the other hand, the stats said that status=2 was rare, so it did use the index and 'instantly' discovered zero rows.

Alas, running an EXPLAIN, even immediately after running the equivalent SELECT does not necessarily give you the explain plan for that select.  (I suspect this explains the mysterious results you got.  I have almost never seen such happen.)

Your test case is not quite correct -- You have only 2 columns, the secondary key and the PRIMARY KEY, so you got Using index;  This is unlikely to happen in the 'real' table -- don't you have other fields?

Please try one more thing to help get to the root of this.  Rerun the tests with

FLUSH STATUS;
SELECT ... ;    -- (returning emptyset)
SHOW SESSION STATUS LIKE 'Handler%';


This will show whether it actually did an index (or table) scan, and was not just a caching problem, as hinted by @jkavalik .