I had thought this problem, an example in the Cilleruelo and Luca paper (which proves that any positive integers is a sum of three palindromes (in base 10)) would be difficult, but four readers found a solution.
Here is DeVincentis's method. The outstanding open question is whether there is an integer B so that every positive integer is a sum of at most B base-two palindromes.
This is a good opportunity for me to attempt to employ the strategy I was envisioning that would solve most numbers as a sum of 2 palindromes.
Write
314159265358979323846 = ABCDEFGHIJKJIHGFEDCBA + LMNOPQRSTUTSRQPONML
21 digits, 21 degrees of freedom in the palindromes. A is necessarily 3, so L is also 3.
314159265358979323846 = 3BCDEFGHIJKJIHGFEDCB3 + 3MNOPQRSTUTSRQPONM3
Now C is going to be 0 or 1, depending on whether D + M carries, so C + 3 does not carry, and B = 1. This then makes M = 3.
314159265358979323846 = 31CDEFGHIJKJIHGFEDC13 + 33NOPQRSTUTSRQPON33
Now D + 3 is going to carry, so C = 0. And then N = 8.
314159265358979323846 = 310DEFGHIJKJIHGFED013 + 338OPQRSTUTSRQPO833
Now E + 8 is going to carry, so D = 7. This makes O = 6.
314159265358979323846 = 3107EFGHIJKJIHGFE7013 + 3386PQRSTUTSRQP6833
Now F + 6 is not going to carry, so E = 7. This makes P = 4.
314159265358979323846 = 31077FGHIJKJIHGF77013 + 33864QRSTUTSRQ46833
Now G + 4 is going to carry, so F = 2. This makes Q = 0.
314159265358979323846 = 310772GHIJKJIHG277013 + 338640RSTUTSR046833
Now H + 0 is not going to carry, so G = 8. This makes R = 1.
314159265358979323846 = 3107728HIJKJIH8277013 + 3386401STUTS1046833
I + 1 is not going to carry, so H = 6. This makes S = 1.
314159265358979323846 = 31077286IJKJI68277013 + 33864011TUT11046833
J + 1 is not going to carry, so I = 4. This makes T = 5.
314159265358979323846 = 310772864JKJ468277013 + 338640115U511046833
K + 5 is now ambiguous as to whether it carries. But J is going to be either 1 or 2, which means J + U will not carry, so K = 0, J = 2, U = 6:
314159265358979323846 = 310772864202468277013 + 3386401156511046833
As already discovered, this algorithm runs into a problem when the first digit and last digit of the sum are the same, or possibly off by 1 if the sum would be forced to carry into the leading digit. In that case, the second palindrome would be forced to end (and thus start) with 0. This problem is resolved by introducing a third palindrome equal to 1.
This algorithm can have trouble with the carries/not carries. It worked out above, but there are certain cases where it fails. In the case where this happens on the last digit, (K, as above), suppose that I needed J + U = 1 (instead of 8) so that this was also ambiguous. Then if I supposed K + 5 doesn't carry, J would be 2, and then J + U = 1 does carry, which makes K + 5 carry, contradicting the assumption. Likewise if I assumed K + 5 does carry, J would be 1, and then J + U would not carry when we needed it to do so!
This carry/not carry can also happen on other digits, and more or less the same thing happens. Again, in these cases we need the third palindrome. However, I am not sure just how bad the carry/not carry problem can get. If I simply make the third palindrome be a 1 (or 2 if it was already 1 to fix the matching first and last digit in the sum) and I cannot guarantee this does not cause other problems elsewhere in the number.
This algorithm also has difficulties when the number of digits in the sum is even. If we had started with ...
3141592653589793238462 = ABCDEFGHIJKKJIHGFEDCBA + LMNOPQRSTUUTSRQPONML
... then there would be 22 digits and 21 degrees of freedom in the palindromes, and we would be in trouble. In the middle, I'd pick K to satisfy K + T = 5, U to satisfy J + U = 9, and then I'd have to pray that K + U = 8, and nine times out of ten it would not. This is probably remedied by making the second palindrome a digit longer, but I am guessing I run into some other problems along the way.