In general complexity is not as important as length, however complexity plus length increase protection against pure brute force password attempts.
Your example of !Pf-4 would be cracked quickly regardless of "complexity" because the number of tries to guess it would maximally be 7,820,126,495 (95^5 + 95^4 + 95^3 + 95^2 + 95) 95 being the number of possible characters. A core i7 will crack that in no time.
For every increase in password length, you increase the number of guesses required by a magnitude of power. The real problem is that most password crackers who know what they are doing use customized dictionary attacks along with brute force attacks which can compromise even long pass phrases fairly easily.
It can also depend on what cryptographic hash was used to hash the passwords. There are known security issues with some hashes like MD5 and there are stronger hashes like bcrypt that are considered "slow" hashing algorithms because they require more time to check each hash.
I would recommend you check out this article on password cracking.
http://arstechnica.com/security/2013/05/how-crackers-make-minced-meat-out-of-your-passwords/2/