I also come to the conclusion that Ruby-like languages are just not the right tool for this kind of problem, but it should be pointed out that you would have been able to solve the 10^14 data set easily, even with Ruby.

I was solving that problem with PHP and got it running reasonably fast (1s per range) for ranges up to around 10^60. PHP is probably faster than Ruby, but it's still in the same area.

The first trick you can use is that you don't have to go through all numbers between start and end, rather you can directly only traverse the palindromes (i.e. you will only have to increment one half of the integer).

The second trick is that only numbers consisting of 0s and 1s (and a 2 at the start/end or the middle) can satisfy the condition (exception: the number "3"). This further massively reduces the search space.

There are more criteria that you can use to narrow down the numbers to consider (e.g. the number of non-zero digits can't be greater than 9). But in the end, cracking the 10^100 range is probably not possible in a language like Ruby or PHP. Using something like C++ on the other hand it becomes a triviality.