The composite factors of prime exponent Mersennes are all base-2 pseudo-primes, but that's not enough; they should probably be Cunningham numbers (which are pseudo-prime to all bases that aren't related to their factors).
I think those are called "Carmichael Numbers"
From: http://www.utm.edu/research/primes/glossary/CarmichaelNumber.html
The composite integer n is a Carmichael number if an-1=1 (mod n) for every integer a relatively prime to n. (This condition is satisfied by all primes because of Fermat's Little Theorem.) The Fermat probable primality test will fail to show a Carmichael number is composite until we run across one of its factors! Although Carmichael numbers are rare, only 2,163 are less than 25,000,000,000, it has recently been shown that there are infinitely many of them.
