Вариант со словарем — хороший. Можно попробовать выжать еще крохи: не делать несколько запросов в хэш-таблицу (причем, скорее всего, в цикле на питоне) для определения кодов стран, а вместо этого мэппинг «код страны» -> «страна» хранить в Trie (или DAWG).
В
github.com/kmike/datrie есть метод longest_prefix_item, которым можно получить самый длинный префикс данного номера и соответствующий ему объект. Записываем в datrie.Trie мэппинг «префикс-страна», вызываем longest_prefix_item и готово.
Вполне может оказаться быстрее (главным образом за счет того, что итерация будет вынесена в C-расширение и не нужно будет создавать копии строк длины 1, 2, 3 и тд). Гарантировать, что будет быстрее, не могу, но, в любом случае, с Trie из питона должно как минимум 1млн номеров/сек получаться.
