O esteemed saint, when I turn on DBI trace (even at maximum level), the only query I see is the one sent to prepare(), which has placeholders. (Can't execute EXPLAIN on it). But say I fill in those placeholders with string datetimes:

 EXPLAIN SELECT logic_id, since, till FROM COND_dummy               
           WHERE logic_id = 9999
           AND ((since >= '2005-01-01 00:00:00' 
                AND since < '2005-01-01 00:00:01')
             OR (till  >  '2005-01-01 00:00:00' 
                AND till  < '2005-01-01 00:00:01')
             OR ('2005-01-01 00:00:00' >= since 
                 AND '2005-01-01 00:00:01' < till))                   
+   
         LIMIT 1;
[download]

It says that it is using my indexes.

+----+-------------+------------+------+---------------+---------+---------+-------+------+--------------------------+
| id | select_type | table      | type | possible_keys | key     | key_len | ref   | rows | Extra                    |
+----+-------------+------------+------+---------------+---------+---------+-------+------+--------------------------+
|  1 | SIMPLE      | COND_dummy | ref  | PRIMARY,IoV   | PRIMARY |       4 | const |    1 | Using where; Using index |
+----+-------------+------------+------+---------------+---------+---------+-------+------+--------------------------+

And just to test the theory that it has something to do with DATETIME and VARCHARS and conversions at all, I changed the DATETIME columns to INT and ran the script again. Exact same behavior. In fact, somehow, using INTs for the since, till columns made everything slower!

[#insert]         [date time]   [ins/s]
     1000 2005-03-09 10:58:10   649.516
     2000 2005-03-09 10:58:14   287.810
     3000 2005-03-09 10:58:19   212.805
     4000 2005-03-09 10:58:26   136.577
     5000 2005-03-09 10:58:34   118.965
     6000 2005-03-09 10:58:45    94.537
     7000 2005-03-09 10:58:57    84.296
     8000 2005-03-09 10:59:10    74.197
     9000 2005-03-09 10:59:26    64.026
    10000 2005-03-09 10:59:44    54.799
[download]

It is a mystery.

There's using an index and then there's utilizing an index. Your query is going to use the composite PRIMARY key because the first column in that key is "logic_id". However, if you comment out the PK and leave only the IoV index, I think you'll find that it's not using the index.

Being right, does not endow the right to be rude; politeness costs nothing.
Being unknowing, is not the same as being stupid.
Expressing a contrary opinion, whether to the individual or the group, is more often a sign of deeper thought than of cantankerous belligerence.
Do not mistake your goals as the only goals; your opinion as the only opinion; your confidence as correctness. Saying you know better is not the same as explaining you know better.

Like this?

mysql> EXPLAIN SELECT since, till FROM COND_dummy                                            
               WHERE ((since >= '2005-01-01 00:00:00'
                       AND since < '2005-01-01 00:00:01')                 
                   OR (till  >  '2005-01-01 00:00:00'
                       AND till  < '2005-01-01 00:00:01')               
                   OR ('2005-01-01 00:00:00' >= since
                       AND '2005-01-01 00:00:01' < till))                           
               LIMIT 1;
+----+-------------+------------+-------+---------------+------+---------+------+------+--------------------------+
| id | select_type | table      | type  | possible_keys | key  | key_len | ref  | rows | Extra                    |
+----+-------------+------------+-------+---------------+------+---------+------+------+--------------------------+
|  1 | SIMPLE      | COND_dummy | index | IoV           | IoV  |      16 | NULL | 9499 | Using where; Using index |
+----+-------------+------------+-------+---------------+------+---------+------+------+--------------------------+

Then it will use the IoV index. I created the two indexes because sometimes the table will be searched specifiying logic_id, sometimes not