You are doing the computation in inexact arithmetic. $11^{16}$ cannot possibly be an even number. In fact, every power of eleven obviously ends in a one.
You're probably doing the computation in doubles. Doubles are only accurate to about fifteen decimal places; after that they round off.
Moreover, you do not need to calculate the whole big number. Use this identity:
$(a \times b) \bmod c$ is congruent modulo $c$ to $(a \bmod c) \times (b \bmod c)$
Make sure that makes sense to you. Take, say, $15$ and $18$, and you want to work out $(15\times 18) \bmod 4$. You could multiply $15$ by $18$ and then divide by $4$ and take the remainder. But think about it like this.
$(15 \times 18) =$
$( (3 \times 4 + 3) \times (4 \times 4 + 2 ) ) =$
$(3 \times 4) \times (4 \times 4) + 3 \times (4 \times 4) + 2 \times (3 \times 4) + 3 \times 2$.
Obviously the first three summands are all divisible by 4, so they go away modulo 4. So
$(15 \times 18) \bmod 4$ is congruent mod 4 to $(15 \bmod 4) \times (18 \bmod 4)$.
Which is equal to $3 \times 2$, so $(15 \times 18) \bmod 4$ is congruent modulo 4 to $(3 \times 2) \bmod 4$, which is a much easier problem to solve.
Do the same thing for powers.
$11^{16} \bmod 17$ is congruent mod 17 to $(11^{8} \bmod 17) \times (11^{8} \bmod 17)$
and the problem is now much easier to solve. Keep going:
$11^{8} \bmod 17$ is congruent $\bmod 17$ to $(11^{4} \bmod 17) \times (11^{4} \bmod 17)$
and now the problem is yet easier. Keep going!
$11^{4} \bmod 17$ is congruent $\bmod 17$ to $(11^{2} \bmod 17) \times (11^{2} \bmod 17)$
And now we have an easy problem to solve. $121 \bmod 17$ is 2, so $11^{4} \bmod 17$ is congruent to $2 \times 2 \bmod 17$. Therefore $11^{4} \bmod 17$ is 4.
$11^{8} \bmod 17$ is congruent $\bmod 17$ to $11^{4} \bmod 17 \times 11^{4} \bmod 17$, so $11^{8} \bmod 17$ is congruent mod 17 to $4 \times 4$, which is 16. Therefore $11^{8} \bmod 17$ is 16.
Similarly, $11^{16} \bmod 17$ is congruent $\bmod 17$ to $16 \times 16$, which is easily determined to be congruent to $1 \bmod 17$.
Therefore $11^{16}$ gives a remainder of 1 when divided by 17. That's a lot easier than doing the big multiplication and the big division, particularly when the numbers get large.
And sure enough, we got one, so that is evidence that 17 is prime.
Finding palindromic primes is not very hard, but rather proving them and labeling them as Prime instead of PRP (Probable Prime) is the hard job. You can find the list of world's largest palindromic primes here
And the reason why proving most of them is time-consuming lies in odd digits in them. That is if you could express your number as $k*2^n +- 1$ then proving is much easier using several algorithms out there, but since palindromic primes usually have more odd digits than $0$ ones, then their finding procedure becomes too long.
As an example, the best palindromic number is of the following form (the smallest one is $101$):
$100000000000...00000000000000001$
It can be easily expressed as $5^n*2^n + 1$ and therefore easy to do primility test. Occurance of a non-zero digit at any position, cause the power of $2$ in the formula to be decreased.
So the best place for such a digits is near the center of number.
Again as an example where power of $2$ is near $n/2$
$100000000000...007700...00000000000000001$
Updated
And for generating the number you can build a simple formula like the following in Mathematica:
Palindromic[n_, digit_, position_] :=
(10^n - 1)/9 + (digit - 1) (10^position + 10^(n - position - 1))
In[1]:= Palindromic[20, 7, 9]
Out[1]= 11111111177111111111
Best Answer
Yes. There are various theorems about prime numbers stating that if $n$ meets condition $X$ then $n$ is definitely a prime number. Some of those theorems depend on $n - 1$, which is a very easy calculation. We can use, for example, the converse of Fermat's "little" theorem to create a Pratt certificate.
Let's say, for the sake of example, that 139 is prime but we're not allowed to use trial division to prove that it is prime (even though a computer can do it in a nanosecond, if even that long).
Clearly 138 is composite, as it's divisible by 2, 3 and 23. We see that $141^{138} \equiv 1 \pmod{139}$. But $$141^{\frac{138}{2}} = 141^{69} \equiv 138 \pmod{139},$$ $$141^{\frac{138}{3}} = 141^{46} \equiv 96 \pmod{139}$$ and $$141^{\frac{138}{23}} = 141^{6} \equiv 64 \pmod{139}.$$
The important thing is that none of those congruences are equal to 1.
So 141 is a "witness" for a Pratt certificate for 139. Of course making a Pratt certificate for 139 is overkill. But for a prime with 139 digits, it's preferable to trial division.
According to Wolfram Mathworld, Wolfram Mathematica uses Pratt certificates for numbers below $10^{10}$ and the more sophisticated Atkin-Goldwasser-Kilian-Morain certificates for larger numbers.