Prove that a counterexample exists without knowing one I strive to find a statement $S(n)$ with $n \in N$ that can be proven to be not generally true despite the fact that noone knows a counterexample, i.e. it holds true for all $n$ ever tested so far. Any help?

The BPSW primality test seems like a good example.  34 years after the probabilistic primality test was described, in daily use in many math packages, we still haven't found a counterexample (even to the weaker versions), and we know from exhaustive testing there are none below 2^64.  Pomerance has a 1984 paper which gives a heuristic argument showing we expect infinitely many counterexamples to exist.  Various authors have constructed lists of primes where the product of some subset is very likely to be a counterexample (the search spaces are enormous however).
