Indexing the difference between two columns in MySQL
You could try MariaDB which supports virtual columns. 


  Indexes are partially supported. Virtual columns do not support
  primary keys and indexes can only be based on PERSISTENT virtual
  columns. PERSISTENT columns can be part of a foreign key and can be
  referenced by foreign keys, but ON UPDATE CASCADE, ON UPDATE SET NULL,
  ON DELETE SET NULL are not allowed.


You could simulate this through your INSERTs or via TRIGGERs (better IMHO) and index the simulated virtual column. Then test to see does that resolve your issue (or at least improve it).

[EDIT in response to the OP's comment]

Yes, indeed, I thought that MariaDB would be a "bridge too far". I really included it for completeness. MariaDB is a drop-in replacement up and including 5.5 (in MariaDB terms). AFAICS, the 10 series is still compatible (it's like MySQL with bits added, but the divergence will only widen in the future AIUI. 

The advantage of using a persisten column is that the persistent column can be indexed whereas the virtual one can't according to the docco that I quoted. 

Has the idea of "simulated" virtual columns worked for you?