Как хранить и искать URL адреса в MySQL?
Храните хеш от урла, его легко можно проиндексировать. И ищите тоже по нему.
Спасибо Arman и Папа Стифлера за подсказки. Решение, которое подошло полностью:

Добавил в таблицу новый столбец типа varchar 
Создал для этой колонки самый обычный индекс
Написал скрипт на Python, который создает hash из URL для каждой строки 
Переписал скрипт проверяющий налчие URL в базе так, чтобы он использовал hash

Теперь, чтобы запросы на существование записи вместо 60 секунд, выполняются в среднем меньше чем за секунду для таблицы с > 1 млн. строк.