Why does mysql stop using indexes when date ranges are added to the query?

Question

I have a table with over 1 million rows, and indexes that look like this:

  PRIMARY KEY (`web_listing_history_ID`),
  UNIQUE KEY `RETS_STAGE1_QUEUE_ID_UNIQUE` (`RETS_STAGE1_QUEUE_ID`),
  KEY `idx_web_listing_history_lookup` (`LN_LIST_NUMBER`),
  KEY `SearchIndex1` (`date_to`,`AR_AREA`,`BR_BEDROOMS`,`BTH_BATHS`,`ST_STATUS`,`LP_LIST_PRICE`,`date_from`),
  KEY `SearchIndex2` (`AR_AREA`,`ST_STATUS`,`date_from`,`date_to`,`LP_LIST_PRICE`,`BTH_BATHS`,`BR_BEDROOMS`),
  KEY `SearchIndex3` (`HSN_ADRESS_HOUSE_NUMBER`,`date_from`,`date_to`,`STR_ADDRESS_STREET`,`_Short_CP`),
  KEY `SearchIndex4` (`date_from`,`date_to`),
  KEY `buildings` (`date_to`,`TYP_PROPERTY_TYPE`,`building_id`,`UN_UNIT`),
  KEY `building2` (`building_id`,`RETS_STAGE1_QUEUE_ID`),

And I have a query that runs reasonably well:

mysql> explain 
SELECT      web_listing_history_ID 
FROM     web_listing_hist 
WHERE AR_AREA IN (8006 , 8007, 8032, 8008, 8033, 8028)         
and (LP_LIST_PRICE BETWEEN 250000 and 350000)         
and BTH_BATHS >= 1         
and BR_BEDROOMS >= 1         
and ST_STATUS IN ('ACTV' , 'BOMK', 'NEW', 'PCHG', 'RACT') 
order by UD_LAST_UPDATE_DATE desc;

+----+-------------+------------------+-------+---------------+--------------+---------+------+-------+---------------------------------------+
    | id | select_type | table            | type  | possible_keys | key          | key_len | ref  | rows  | Extra                                 |
    +----+-------------+------------------+-------+---------------+--------------+---------+------+-------+---------------------------------------+
    |  1 | SIMPLE      | web_listing_hist | range | SearchIndex2  | SearchIndex2 | 7       | NULL | 16530 | Using index condition; Using filesort |
    +----+-------------+------------------+-------+---------------+--------------+---------+------+-------+---------------------------------------+
    1 row in set (0.00 sec)

That is, until I decide to take advantage of my Data Warehousing SCD-style columns to limit the results based on a couple of additional date criteria

adding this to the WHERE clause

'2015-05-31 23:59' BETWEEN date_from 
AND date_to AND date_from > '2009-11-27 14:37:18.0'

results in this horrific table scan...

mysql> explain 
SELECT      web_listing_history_ID 
FROM     web_listing_hist 
WHERE     '2015-05-31 23:59' BETWEEN date_from 
AND date_to         
AND date_from > '2009-11-27 14:37:18.0'         
and AR_AREA IN (8006 , 8007, 8032, 8008, 8033, 8028)         
and (LP_LIST_PRICE BETWEEN 250000 and 350000)         
and BTH_BATHS >= 1         
and BR_BEDROOMS >= 1         
and ST_STATUS IN ('ACTV' , 'BOMK', 'NEW', 'PCHG', 'RACT') 
order by UD_LAST_UPDATE_DATE desc;
+----+-------------+------------------+------+--------------------------------------------------+------+---------+------+---------+-----------------------------+
| id | select_type | table            | type | possible_keys                                    | key  | key_len | ref  | rows    | Extra                       |
+----+-------------+------------------+------+--------------------------------------------------+------+---------+------+---------+-----------------------------+
|  1 | SIMPLE      | web_listing_hist | ALL  | SearchIndex1,SearchIndex2,SearchIndex4,buildings | NULL | NULL    | NULL | 1063830 | Using where; Using filesort |
+----+-------------+------------------+------+--------------------------------------------------+------+---------+------+---------+-----------------------------+
1 row in set (11.02 sec)

What am I possibly doing wrong?