It's not clear that Marsaglia's tests are really good enough. See this Stack Overflow discussion.
Kolmogorov complexity is not the right criterion for statistical randomness tests, since any pseudorandom sequence has low Kolmogorov complexity. What you really want in a random number generator is for the sequence to be computationally pseudorandom; that is, without knowledge of the seed, no polynomial-time test can distinguish the sequence from a truly random sequence.
In fact, there are a number of random number generators which are believed to be computationally pseudorandom. Nobody uses these, however, partly because they are computationally too expensive, and partly because of inertia and partly because the existing pseudorandom generators we have are good enough most of the time. A while ago, for one of the most common methods of pseudorandom number generation (linear congruential), I ran into cases where they unexpectedly produced the wrong answer.
Marsaglia's tests were developed over a number of years, and I believe each was designed to fix certain flaws that many pseudorandom number generators contained at the time. Once good-enough pseudorandom number generators were available, nobody bothered creating a more stringent series of tests.