Why does MySQL only sometimes use my index for a range query?
The general behavior of the MySQL Query Optimizer is as follows: If less than 5% of the rows of a table has to be traversed in an index, the index is used. Otherwise, the index is dismissed and a full table scan is done.

Now look at the index: (startBlock,endBlock).

Here are two questions


How many netblock up to the third octet do you have for startBlock ?
How many netblock up to the third octet do you have for endBlock ?


To get a hold of the distribution of netblocks, run this query

SELECT *,
    IF(ABS(endNetBlock - startNetBlock) &gt;= 256,1,0) NotWithinSameRange,
    IF(startNetBlock - endNetBlock &gt; 0,1,0) StartRangeAheadOfEndRange
FROM
(
    SELECT COUNT(1) rangeCount,startNetBlock,endNetBlock
    FROM
    (
        SELECT
            (startBlock - MOD(startBlock,256)) startNetBlock,
            (endBlock - MOD(endtBlock,256)) endNetBlock
        FROM geoIP
    ) AA GROUP BY startNetBlock,endNetBlock
) A


This will give you a general idea of


how many netblock combinations you have
presence of any invalid ranges


If NotWithinSameRange or StartRangeAheadOfEndRange are 1 in any instance, that range has to be clenaed up. You have to be sure that all netBlocks are properly represented.

If you have StartRangeAheadOfEndRange=1, that is a definite problem.

I hope these suggestions provide food for thought.