How to strike a balance between security policies and practical implementation challenges?
Since this question is not a technical one, rather more about human behaviour, you won't get the answer. What you describe is very typical though and I made the same experience.
Complex password rules will usually not lead to more safe passwords, really important is only a minimum length, and a check against a list of the most used passwords. People cannot remember tons of strong passwords, and such rules can even interfere with good password schemes. People can get very inventive to bypass such rules, e.g. by using weak passwords like "Password-2018", which satisfies most rules. Often you end up with weaker passwords instead of stronger ones.
The same applies to the password-change rule, it is very common to add an increasing number or the current month to the password.
Recently NIST published an official paper (see chapter 10.2.1), advising against such rules, and against its former recommendations.
A try to answer the edited question:
- We can try to delegate authentication, either with single-sign-on or with OAuth2, this way we can reduce the passwords a user has to remember (same password for multiple services).
- One could recommend a password-manager. A link on the login page to a good tool won't hurt.
- We could engourage password-phrases. Why not place a funny example on the login page: "I like to sleep until it is too late to get up", this raises awareness and shows the user how much easier (and mobile-friendly) pass-phrases can be. Just make sure to reject this exact example.
The best solution is to train your user base to use passphrases.
Passphrases are easier to remember, easier to type - and harder to crack. And the NIST rules that @martinstoeckli mentioned are designed to be passphrase-friendly.
Five random words, drawn from a dictionary of at least 20,000 words or so, would be a nice middle ground.
Training will be key, using materials like Stanford's.
You could even create a way to generate and suggest passphrases to them. It would be relatively easy to create a simplified, private instance of ae7.st/g or rempe.us/diceware for your user base to use as a starting point. These execute entirely on the client side, so the passwords cannot be collected remotely.
[Edit: Yes, I'm also a big fan of password managers. But the original question is focused on password-reset helpdesk calls in the enterprise, which almost certainly means AD passwords - which are one of those "front end" passwords that usually must be memorized.]
Help everyone in your organization use a good password manager. (I should disclose that I work for the makers of a very fine password manager.)
Seriously, you have a password management problem, and using a password manager within your organization is the best shot at addressing it. This is what password managers are designed to deal with.
Addressing comments
There have been a number of excellent comments my rather off-hand answer. So it looks like I'm going to have to put in some real effort here.
There are two questions to discuss.
Forgetting the password manager password
A password manager does not eliminate the need to remember all passwords, but certainly does help. It wasn't entirely clear to me whether the original question was focused specifically on the workstation/AD/LDAP user password for the organization or other passwords as well.
One thing about using password manager is that you typically need to type it its password several times a day. So after a short while, people do learn it well.
And talking specifically of 1Password, we have things set up so that it is impossible for us learn anyone's secrets, but it is possible for certain individuals within an organization to be empowered to perform recovery. See either our documentation for what this looks like to an administrator or our security white paper for the gory details of how that all works behind the scenes.
Workstation login
Of course you can't run your password manager on a system that you can't log into. But depending on your organizations policies, the password manager can also run on a user's phone.
I understand that there will be some objections to this, but consider that it is in the organizations' interest that people's sign on password not be something that they also use for the HTTP only MyKittyPictures.org which is built on a version of Wordpress that hasn't been updated in a decade. So you do want your people use a password manager at home as well as at work.
Again, 1Password (and some of our competition) allows ways of managing separate accounts, so that you don't find workplace secrets leaking into places you don't want it to. I didn't really want to turn this into a sales pitch, but there are ways to set things up that work for the security needs of various organizations.
With unique passwords, the need for forced rotation diminishes
(This is relevant because forced password rotation leads to people forgetting passwords or using crappy ones.)
Forced password rotations generally do more harm than good. Some of the "good" that they do is because people tend to reuse the same password on multiple services, and so once one gets compromised the everything using that same password is vulnerable.
Getting people to use a password manager helps move people away from password reuse.
With generated passwords, complexity rules aren't needed.
Password complexity rules may also do more harm then good, and they certainly lead to passwords that are hard to remember. 1Password nudges people toward very strong, but usable, master passwords.
Again, I'm not trying to turn this into a sales pitch. Look at what we offer (talk to us about your specific organization's needs), but look at others as well. We are the best, in my not so humble opinion, but my over all point is that many of your password problems can be addressed through the use of a password manager. And it will get your people engaging in more secure habits. A password manager enjoys the happy spot of both increasing security and making life easer for users.