Mysql – Slower running Query with better Filter

mysql> SELECT  *
    FROM  history_uint h
    WHERE  h.itemid='1825689'
    ORDER BY  h.clock DESC
    LIMIT  2 OFFSET 0 ;
Empty set (0.00 sec)

Explain:

               id: 1     
      select_type: SIMPLE
            table: h  
       partitions: 2016_02_18,p2016_02_19,p2016_02_21,p2016_02_22,p2016_02_23,p2016_02_24
             type: ref 
    possible_keys: history_uint_1
              key: history_uint_1
          key_len: 8
              ref: const
             rows: 1
         filtered: 100.00
            Extra: Using where 

This is the problem query, which takes over 40 min to return 0 rows:

mysql> SELECT  *
    FROM  history_uint h
    WHERE  h.itemid='1825689'
      AND  h.clock>1456091116
    ORDER BY  h.clock DESC
    LIMIT  2 OFFSET 0 ; 

Explain:

             id: 1   
    select_type: SIMPLE
          table: h   
     partitions: p2016_02_21,p2016_02_22,p2016_02_23,p2016_02_24
           type: range 
  possible_keys: history_uint_1
            key: history_uint_1
        key_len: 12
            ref: NULL
           rows: 1
       filtered: 100.00
          Extra: Using index condition

Here is the table:

mysql> show create table history_uint\G
*************************** 1. row ***************************
       Table: history_uint
Create Table: CREATE TABLE `history_uint` (
  `itemid` bigint(20) unsigned NOT NULL,
  `clock` int(11) NOT NULL,
  `value` bigint(20) unsigned NOT NULL,
  `ns` int(11) NOT NULL,
  KEY `history_uint_1` (`itemid`,`clock`)
) ENGINE=InnoDB DEFAULT CHARSET=latin1
/*!50100 PARTITION BY RANGE ( clock)
(PARTITION p2016_02_18 VALUES LESS THAN (1455840000) ENGINE = InnoDB,
 PARTITION p2016_02_19 VALUES LESS THAN (1455926400) ENGINE = InnoDB,
 PARTITION p2016_02_21 VALUES LESS THAN (1456099200) ENGINE = InnoDB,
 PARTITION p2016_02_22 VALUES LESS THAN (1456185600) ENGINE = InnoDB,
 PARTITION p2016_02_23 VALUES LESS THAN (1456272000) ENGINE = InnoDB,
 PARTITION p2016_02_24 VALUES LESS THAN (1456358400) ENGINE = InnoDB) */
1 row in set (0.00 sec)

Why does one query run faster than the other? And why is there such a big difference? Seems/feels like it's doing a full table scan?

The code uses h.itemid = '1825689' and not h.itemid = 1825689 (without quotes, though it is an integer column). It's the way it comes from app, but it shouldn't make a big difference. Execution plans are the same with quotes and without, as well as run time. First one, where is only itemId returns in milliseconds, second one that has itemId and clock runs for 40+ min.

I am using MySQL 5.7.10. I have run many permutations of that query already, and the one specifically without the quotes is still running, 7min + so I am guessing quotes made no difference.

Adding a Link to Explain Plan with JSON Format