Why does adding ORDER BY makes the select much faster?
What was the IP?  1.1.1.1 would do best by starting from the beginning.  255.255.255.255 would work better by starting at the end.

The EXPLAIN does not say whether the "range" was scanned ascending or descending.  I don't even think EXPLAIN FORMAT=JSON SELECT ... would point this out.

So... I think your fast one had a high IP address and did start from the end due to the ORDER BY.

More discussion of the intractability of queries like this, plus a solution if the ranges are non-overlapping.