A reasonably complex password is required, but realistically it's probably necessary - in addition - to have an audit policy in place. Is there suspicious usage of accounts? Are account being used in new and unexplained ways?
I don't know how you'd do that in an automated fashion that would be smart enough to catch unusual usage. I expect that few companies would be willing to dedicate a person or more to watching account activity.
Maybe an additional statement like: "All activity on the corporate computers may be logged. You are responsible for the security of your account. Treat it like your Social Security number..." would help people to take passwords seriously.
IMO, having a reasonably complex password that people can remember is much more important than changing them every 30 days. If they're complex and frequently change, then people will make cheat sheets. If things are audited, then I think yearly password changes are more than sufficient (and/or requiring changes when people leave).
Cards or fingerprint readers is probably much more secure than complex, frequently changed passwords, given human nature.
My $0.02.
Cheers,
Scott.