The basic issue is that passwords, as a security mechanism, stink.
If you ask people to change them often, they write them down. If you ask them to use 30 letter passwords with at least 3 numbers, 4 upper case letters, and a control character, they forget them or write them down or do other silly things. If they're simple, users will use stupid password like bunny7 or Bunny7. And they'll use the same bad password for everything, including their porno account and their hotmail account.
I like tools like Mobile OTP, which allow users to use their cell phone as a two factor authentication tool.
In the long term, it is likely that we will somehow land in a world with encrypted certs as the user identification mechanism. Things like OpenID and CAS simplify user authentication and allow convenient single-signon.
In the long term, the best bet is to reduce the number of times users need to issue credentials -- get rid of the "HR" password and the "time-sheet" password and the "CRM" password. Unify them into a common authentication infrastructure that requires users to issue their credentials once. Then have them use something like MobileOTP or an RSA SecurID that uses two-factor authentication.
In the short term, password policies are going to be the topic of religious wars. Just do whatever your boss asks you to, and if you're the boss, use your judgement based on your user-base and expected security profile.
Good luck!