The best and most reliable solution is to use a 3rd party software solution that proactively notifies users of upcoming password expiration.
The best software tool that I have found is Password Reminder PRO from SysOp Tools.
It’s low cost, easy to setup / deploy and can be used free for 60 days. It also allows you to test in your live domain without disturbing users. Highly recommended, definitely makes up for the noted issue.
This would be a good tool in a small organization, sending reminder to a community of about 20,000 users will generate traffice on the network and possibly queue on your messaging system. Password Policy has its disadvantages but with user education you should not have need of this tool.
You can create a Group to identify these categories of users and a Group Policy to relax their password age.
Above all, what did the company policy say about Password Policy? That is what MUST be followed.