The answer is that it's not that simple. It's important to understand all of the approaches to attacking passwords before you can say that complex is good or bad, as the different requirements are intended to deter different types of attacks.
As you point out, given two equally long passwords from the same character set, password complexity requirements do reduce the overall search space. For example, given a 1 character ASCII password that must include a letter vs a 1 character ASCII password that may be anything, it's easier to guess the first password.
But password character requirements should not be used in exclusion of length. Consider the following password requirement sets' minimum strength:
- 8 printable ASCII characters = roughly 100^8 = 10^16 possible values
- 16 printable ASCII digits = 10^16 possible values
- 9 printable ASCII characters with at least 1 number, 1 letter (of any case) and 1 symbol = ((10 numbers)(52 letters)(30 symbols)*100^6) = 10^16
[NOTE: I know that 100 is not the true number, it just makes the math easier]
So we see that three different password requirements are equally strong, in terms of brute force requirements. But we haven't done anything about dictionary attacks. In a dictionary attack, we simply test a list of well known words and see if any of them is the password. Make any of them longer and you've made it stronger than the others.
Password requirement 1 does nothing to prevent dictionary attacks, and 3 does little. You can use the word "prevents", which is extremely likely to be found in a dictionary. You can look at real password lists that have been leaked on the internet (or create your own popular service and collect passwords) and discover popular passwords to optimize your attack for the most likely values (ex. if everyone in New York picks a variation of "Yankee1!", then your attack will start by trying variations of "Yankee1!").
So the next natural thing to do is to prevent passwords that are dictionary words. This reduces the number of valid passwords, but it also removes an optimization available to the attacker. Make the password a little longer and you can keep the no-dictionary-words password equally strong or stronger.
But this does nothing for leet speak passwords. You won't find P4$$w0rd in a dictionary, but it's a pretty standard variation that brute forcing tools test. Take every word in the dictionary, run it through leet speek, prepend, postpend, and insert one or two other characters at every location.
Password complexity requirements can then be introduced to restrict these types of attacks - multiple symbols, multiple numbers, and a (yet again) longer password. Something that requires a password management tool to track. It's hard to brute force (because it's ever longer) and it's hard optimize because it's not in a dictionary or like anything in a dictionary).
But what happens when you break a particular password, and the user changes to a new one? Users often try to do the easy thing, and pick an easy to remember password - one very similar to the previous. P4$$w0rd1 becomes P4$$w0rd2. But the attacker will simply add P4$$w0rd1 to his dictionary, and he'll automatically test for P4$$w0rd2. So re-use of passwords is often disallowed.
But the heart of the issue is, "Is it suitable to the organization's needs?" You need a password that is strong enough to be secure for as long as it is useful (ex. it is changed or the account is disabled), given all other compensating controls that we haven't even started talking about. If the brute forcing speed is slow, or you only get a few chances, weaker passwords are okay (ex. IronKey allows something like 17 attempts and requires physical access, so a 10^16 password is more than strong enough).