Offline, the attacker can if all else fails brute-force the password. No password is complex enough to survive a brute-force attack. With the growth in computing power, including the ability to apply GPUs and specialized hardware to the task, search space size alone isn't enough protection. The only protection, as noted, is detecting the leak of the password database early so users can change passwords before the offline attack has yielded usable results. Alternatively, the authentication system can employ two-factor authentication so that the password alone isn't enough to compromise the account.
For on-line attacks, I'd argue the number given's too large. A properly-designed on-line system should be designed with rate-throttling and account-locking mechanisms, and with those in place a password should only need to survive at most maybe 10 attempts before even the correct password won't access the account. Those mechanisms can be applied to all current systems right now.
The biggest hole isn't the password itself, it's the password-recovery system. Why bother with either an offline or on-line attack on the password when you can initiate password recovery and change the password on the target account to one you know?