It is not true that iterating almost always seems to lead to a palindrome. Unless iterating leads to a palindrome "fairly quickly," one almost never seems to arrive at a palindrome. For a number with few digits, an eventual palindrome is fairly likely. As the number of digits grows the likelihood seems to decrease rapidly. Let $s(x)$ be the result of applying the reverse and add operation to $x$. There is no proof which rules out the possibility that for all $x$ there is a $j$ with $s^j(x)$ a palindrome, but it seems highly unlikely. If we examine a large range of numbers and classify $x$ as a probably never getting to a palindrome if none of $s(x),s^2(x),..s^{50}(x)$ is a palindrome then we will have some errors (probably under $1\%$) which can be discovered by pushing out to $s^{500}(x)$. But if we push out that far, or even just to $s^{300}(x)$ then we are likely to never have an error (that we can discover.)
There is (according to Wikipedia) a 19 digit number which arrives at a palindrome after 261 iterations and this is the current record. I tried 500 random 10 digit integers (actually, random integers under $10^{10}$) 10^{10}.$) Of them, 224 went to 300 iterations without a palindrome. There were 13 cases which did arrive at a palindrome but taking at least 30 iterations. They took 30,30,32,32,32,34,38,41,42,46,49,66 and 88 iterations.
Call $x$ special if no carries occur in the addition $x+r(x).$ In this case $x+r(x)$ is a palindrome. Call $x$ exceptional if $x+r(x)$ is a palindrome but $x$ is not special (i.e. some carries do occur).
There are exceptional integers such a $30008$ but how common are they?
Suppose that $N=2M$ is even. Then there are about $10^M$ $N$ digit palindromes. However there are over $50^M$ $N$ digit integers $y=\sum_0^{N-1}a_i10^i$ so that By definition, $s(y)$ s(x)$ is a palindrome . This is because there are $55$ ways to choose each pair of digits $a_i,a_{N-1-i}$ so that $y$ is special. Of course there are only $54$ choices exactly when $i=0$ since $0,0$ x$ is ruled out. Also, that count includes the $y$ which are already palindromesspecial or exceptional.
If $y$ has an even number of digits then $s(y)$ will be a multiple of $11.$ If $y$ has $2M-1$ of digits then $s(y)$ differs from a multiple of $11$ by a $2a_M10^M.$
If $y$ is a multiple of $11$ so is $r(y)$ and hence also $s(y)$ and all further iterates $s^i(y).$
If $z=s(y)$ then when we appropriately match up $z$ with $r(z)$, corresponding digits will be equal or differ by $1$ (in case of a carry immediately before one but not the other.) Here appropriately means that when $Z$ z$ has one more digit than $y$ we do not match the leading $1$,
So, if $x$ has an even number $2M$ of digits then $s(x)$ is a multiple of $11$ which, if not a palindrome, misses it only by having some positions which should be equal differ by $1$ and perhaps having a leading $M+1$st 2M+1$st digit which is a $1$. If $x$ has an odd number of digits then almost the same is true.
The previous comments shows that integers of the form $s(x)$ are fairly special. What can be said about numbers of the form $s^2(x)$, $s^3(x)$ etc? Certainly by $S^6(x)$ s^6(x)$ (and usually earlier) we have had an even number of digits at some earlier stage and hence are at a multiple of $11$ from then on.
Clearly there must be many solutions of $s(x)=s(y)$ with $x \ne y$ since the the image set is much sparser. We can see that directly because for $y=\sum_0^{N-1}a_i10^i$ we have $s(y)=\sum_0^{N-1}(a_i+a_{N-1-i})10^i$ s(y)=\sum_0^{N-1}(a_i+a_{N-1-i})10^i.$ This usually presents many chances to increase one of $a_i,a_{N-1-i}$ by $1,2,3$ or even more and lower the other by an equal amount to get $x$ with $s(x)=s(y).$
It has not been ruled out that (for base 10) eventually $s^j(x)$ is always a palindrome, but this seems exceedingly unlikely. If we examine a large range of numbers and classify $x$ as a probably never getting to a palindrome if none of $S(x),s^2(x),..s^{50}(x)$ is a palindrome then we will have some errors which can be discovered by pushing out to $s^{500}(x)$. But if we push out that far, or even just to $s^{300}(x)$ then we are likely to never have an error (that we can discover).
Recall that every $y$ with $s(y)$ a palindrome is special or exceptional (and vice versa). I have not studied how rare exceptional numbers are. I would expect very rare, it should be easy to check. Roughly $2^{-N/2}$ (1.8)^{-N/2}$ of the $N$ digit integers $z$ are special and I do not see that knowing also that $z=S^j(x)$ z=s^j(x)$ for some $x$ changes that. So for small starting $x$ there is a reasonable fair chance of getting to a special number as we repeatedly apply $s$. However this chance gets smaller as the number of digits rises. This suggests that if iterating $s(x)$ gets into enough digits without running into a palindrome, it is unlikely to ever arrive at one.
Here is some justification of the counts: Let $N=2M$ be even. There are $9\cdot10^{N-1}$ integers $x=\sum_{0}^{N-1}x_i10^i$ with $N$ digits. The proportions of these which are special and exceptional are easy to give exactly but less than $\frac{1}{1.8^M}$ of them are special and and less than $\frac{1}{10^M}$ are exceptional. This is because there are $100$ ways to pick each of the $M$ pairs $x_i,x_{N-i-1}$ (except for $90$ ways to pick $x_0,X_N$.) To be special there are only $55$ choices with $x_i+x_{N-i-1}\le 9$ (except $45$ for $i=0$). A number is exceptional if each pair $x_i,x_{N-1-i}$ has sum $0$ or $11.$ (I think I proved that to my satisfaction.)For $N=2M+1$ the ratios are about the same taking into account the central digit.
Final thoughts Here is a more simple an easier related problem of which might be called the 49 problem, I don't know if there is a similar nature49+49=98 problem although we have just looked at the 98+98=196 problem. 196+196=392 and I've spent time on the 392 problem but it is unrelated. Here is the 49 problem: Call an integer $z$ very even if all digits are even (equivalently, it is equivalently,if $d(x)=x+x$ z=d(x)=x+x$ for an $x$ with all digits less than $5$) .
Up to 20001 there is a single starter which gets to a very even number after 47 doublings but no sooner. Curiously 49,98,196,392,... is the first example which never arrives seems to arrive at a very even number. I did not actually prove that but included this example because I am sure that thought there is an easy would be some integers which provably never lead to a very even number. My proposed proof based on the fact was that the sequence $x,d(x),d^2(x),\cdots$ is eventually periodic mod $10^j$ for any $j$ j$, so one would just need to find the appropriate $j$. j$ where every member of the cycle had an odd digit. (updateHowever now I see that the appropriate (eventual) orbit mod $\mod 10^j$ orbit has length $4\cdot 5^{j-1}$ so is almost sure to surely does have a $j$ digit very even member.member (which may be the tail end of much much longer integers with plenty of room for odd digits.) However it seems clear that when the number of digits is small there is a reasonable chance of bumping into a very even number but that goes to $0$ exponentially in $d$ for a "random" $d$-digit number. It would be nice to find some invariant for your problem, or for this one, (similar to the proposed reduce mod $10^j$ here) which could rule out a palindrome. Something like: "add all the digits, if the number of digits is odd then add in the middle digit again, reduce mod $2m$" A palindrome would have to give an even result. Short of something like that it seems hard to imagine a definitive proof (as opposed to probabilistic hueristicheuristic) of never arriving at a palindrome.
