>Another alternative is to just send "update your password" emails to everyone framing it as an improvement to your site's security.

I guarantee everyone with a decent spamfilter will miss those e-mails - that looks exactly like a standard phishing attempt.