Well, any non-zero multiple of $10$ will give trouble! It must end in $0$, and unless we pad the front with $0$'s, we cannot get a palindrome.
If $a$ is relatively prime to $10$, then $a$ divides the extremely palindromic $10^k-1$ for some $k$. This can be proved by using Euler's Theorem, which says that in that case $10^{\varphi(a)} -1$ is divisible by $a$. Here $\varphi$ is the Euler $\varphi$-function.
Remark: If we allow front padding by $0$'s, we can always find a palindromic multiple of $a$. If $a$ is divisible by neither $2$ nor $5$, that is dealt with above. Otherwise, multiply $a$ by $2$'s or $5$'s until we get a number of the form $b\times 10^k$, where $b$ is relatively prime to $10$. Some multiple of $b$ is all $9$'s. So some multiple of $b\times 10^k$ is almost palindromic, except for trailing $0$'s. It can be made palindromic by padding with leading $0$'s.
We saw that if we want a fully palindromic multiple, $a$'s divisible by $10$ are no good. But it seems plausible that unless $a$ is divisible by both $2$ and $5$, it has a palindromic multiple.
I've tried solving the same problem yesterday. I managed to brute-force my way to finding all fair and square (palindromes whose square root is a palindrome) numbers from 1 to $10^{14}$:
1, 4, 9, 121, 484, 10201, 12321, 14641, 40804, 44944, 1002001,
1234321, 4008004, 100020001, 102030201, 104060401, 121242121,
123454321, 125686521, 400080004, 404090404, 10000200001, 10221412201,
12102420121, 12345654321, 40000800004, 1000002000001, 1002003002001,
1004006004001, 1020304030201, 1022325232201, 1024348434201,
1210024200121, 1212225222121, 1214428244121, 1232346432321,
1234567654321, 4000008000004, 4004009004004
My solution was correct, and the second dataset was solved. But I couldn't find a proper way to calculate all fair and square numbers up to $10^{100}$.
I showed this to my wife this morning, and she noticed an interesting pattern of numbers within my list:
121, 10201, 1002001, 102030201, 10000200001, 1000002000001
484, 40804, 4008004, 400080004, 40000800004, 4000008000004
12321, 1002003002001,
Some fair and square numbers re-appear with space padding. Let's try beyond $10^{14}$. Adding some zeros to $1020302030406040302030201$, whose square root is $1010100010101$ - a palindrome!
Wish I had my wife with me when I solved this yesterday.
I don't have a mathematical explanation for this phenomena, but I guess that for some reason, every fair and square number beyond a certain boundary can be built by adding zeros to a smaller palindrome.
Best Answer
The formulation given (with smaller factors having leading digit 9) does not work for palindromes of all lengths. For example:$$3 \times 3 = 9$$ $$37 \times 27 = 999$$
So the problem expressed in that form needs to be restricted to palindromes having an even number of digits.
And the part of the question which seems currently to be open is -
Given $n>0$ is there a palindrome having $4n+2$ digits, and leading digit (most significant digit) equal to 9, which is the product of two integers each having $2n+1$ digits?
Notes: the two smaller integers will necessarily have leading digit 9. The largest palindrome of this kind will necessarily have leading digit 9, provided we can find at least one example - though the example we find need not be the largest. For $n=0$ there is no answer, because $9 \times 9 = 81$, which is less than 90, and all two digit palindromes are divisible by 11 (which is prime).
Some construction rather different from the one illustrated will be necessary to tackle palindromes with odd numbers of digits.