What actually matters is not the key space when it is so vast. Without these requirements: number, special char etc, the passwords used in practice would often just be dictionary words, and a dictionary is a much smaller key space.

Maybe the best countermeasure would be to match users passwords against a dictionary,