Group Policy “Maximum password age” fails to apply

In my Windows network with all AD servers (still) running Windows 2003, I encounter the following problem: The "Maximum password age" policy apparently does not apply. Even though some of the users have indeed been asked to change their password regularly, apparently very many are not asked to do so. A quick LDAP search for users with passwordLastSet <= two years(!) ago, lastlogonTimestamp >= three weeks ago, and userAccountControl=512 (this cryptic condition means especially that the Password never expires checkbox is not checked) gives me a list of about 70 (!) users. I might manually request them to change their passwords upon next logon, but I would prefer to see the password age policy do its work (and I left them unmodified precisely to get an indication of the policy working).

I thought I knew where to configure this: in the Default Domain Policy under Maximum password age, period.

I mad the following out of desperation, which according to the docs should not have helped (but at least it should not harm either, should it?): Since the setting in the "Default Domain Policy" – apparently – had no effect, I addtionally made corresponding settings in about all policy objects that might have influence under various circumstances, that is "Default Domain Controllers Policy", "[COMPANY] Domain Policy", "[COMPANY] DC Policy", "[COMPANY] Computers Policy" (the names suggest their scopes quite well, I guess)but nothing helped.
To give an overview: People log in first to their PC, which can be about any version of Windows, from 8.1 down to a few even still running XP (and in the process of being dumped). Here they either work locally or, mostly, login to RDP servers, which all run Windows 2008R2; this latter login is additionally governed by a specific "[COMPANY] TS Loopback Policy", in which I also added the maxpassword age setting – without success. And after all, already the login to the local PC should have triggered an expiry.

In other words, I have no idea what could be the problem behind this and woould greatly appreciate help.
Meanwhile this has been background-bugging me for a few months now and in fact now it is becoming a growing pain in the neck (see the actual password ages discovered in the first paragraph!!). While we eagerly want to migrate the AD version and this might resolve the prblem as a side-effect, we would be much happier if this problem could be resolveed before starting that migration (and possibly importing a deeply hidden problem).