After nearly two weeks of going nuts trying to setup a password policy, I finally found part of the documentation that I was missing. Apparently "ppolicy" does not actualy enforce the policy you create. If I'm understanding the documentation correctly, it really only provides more of a transport to something else which can do it.
In particular the attribute pwdCheckModule, needs to point to a module which can enforce the policy. However no module seems to be provided.
What modules are other people using? I stumbled around and found password_check.so, which I am trying to setup now with partial success.
Anyone else have something better? One thing I need to do which I don't think this will help with, is storing the last x passwords.