The same NIST document (800-63) that recommends against password expiration also recommends against complexity requirements, instead organizations are supposed to develop a list of bad passwords that would likely be used in an external dictionary attack.
People understandably get really fired up by the idea of not having to change their password every 90 days, but forget that the guidelines are a package that contains a lot of "shall"s (no password expiration is a mere "should") that would be more painful for organizations stuck with a lot of legacy software, like the requirement to use two authentication factors and the use of secure authentication protocols.