Was having fun reminding myself of the inner workings of a few primality tests today and wondered if there exists a composite number that (perhaps provably) passes all known tests? (Ignoring tests which are 100% accurate such as trial division).
If so how rare should such numbers be?
There are no known counterexamples to the simple BPSW test (after 34 years and much searching). Which is why most math software uses it. However we believe infinitely many counterexamples exist -- one reason why paranoid people add on at least one random-base M-R test. As Daniel Fischer points out, once a random base is used then a given composite will not provably pass it.
For the old-timey (but still sadly commonly used) method of running Miller-Rabin for the first N bases, there are constructive methods for producing counterexamples (Arnault), so for that testing method the answer is most certainly yes.
There are some other probabilistic compositeness tests that have no known counterexamples, but they've had much less time and effort spent looking. One may, for instance, intersect a Frobenius test with BPSW, but this just reduces the probability. I don't think (but could be wrong) there is any anti-correlation between Frobenius tests and Lucas/strong-probable-prime tests.
AKS and APR-CL are both deterministic tests. If we're going to ignore run times, then there are other well known options. But you asked for tests that are not 100% accurate, leaving us with compositeness tests.