Если получше изучить структуры базы, по какому принципу она строится, то, возможно выражение
SELECT country_id, ip_from
FROM tbl
WHERE ip_to > a
ORDER BY ip_to
LIMIT 1
можно будет использовать без сортировки, т.е. :
SELECT country_id, ip_from
FROM tbl
WHERE ip_to > a
LIMIT 1
Не уверен, что даже когда ip_to - индекс, mysql не будет использовать ORDER BY. Хотя оптимизатор mysql возможно первое выражение сам упрощает до второго
А проверку на IP, если не сложная то можно сделать и в коде.
Да и все зависит от того какая нагрузка на сервак. Если ты создаешь специализированный сервис с десятками тысяч запросов в секунду, то лучший вариант, конечно, писать специализированный скрипт, заточенный именно под работу с известным набором данных.
=====
а то что после добавления and ip_from < A возвращаются тормоза, то здесь следует глянуть а какой у тя индекс в данном случае.
Минусом конечно то, что индекс занимает хорошую долю памяти. Можешь посчитать.