The key insight is to see that there's a one-to-one correspondence between 128-bit strings and 256-bit palindromes.

Has it been proven that there is a one-to-one relationship between public keys and private keys in ECDSA with the secp256k1 curve?  If not, then there is no way to know the answer to your question, since there is no way to know what values are valid public keys without first calculating all of them.

That is going to depend on the format of the key I suppose.

Binary? (I think it would be 2¹²⁸, right?)
Hex?
Base 10?
Base58Check Wallet Import Format?
Mini Private Key Format?
Base 62?
Base 64?
Extended Ascii (Base 256)?

 

Guess I'm just being a PItA at this point.  I suspect that you mean Base58Check Wallet Import Format.

Ok, lets assume you are only referring to Wallet Import Format of uncompressed keys. If I properly recall the specifics of the forma that means the private key should be 51 characters long and always start with either 5H, 5J, or 5K.
The next 24 characters can each be any of 35 different characters.

I'd think that would work out to something like:
3 x 35²⁴

Does that work out to something like 3 x 10⁴⁸