Is Mersenne primality testing necessarily EXPTIME?
Nothing is impossible. But the problem is that you might want to check whether a 10 million digit number is a prime, but that number is just 2 raised to an 8 digit power, minus 1, so the problem size would be just 8. 

For random 10 million digit numbers, the problem size is 10 million. For 10 million digit Mersenne numbers, the problem size is just 8. You can't even write down that number in polynomial time in the problem size. You can't even write it in base 2 in polynomial time, where the number is just a huge string of 1's.