Love the suggestions you gave so far, I'll be keeping them in mind for future reference!
My #1 suggestion would be to attack your own employees. I don't mean you should run around with an axe all "Here's Johnny!" style, screaming at people about proper security practice, but rather stage cyber-attacks and judge their responses, then explain to them what they did right / wrong. People learn through experience much better than they learn through reading an email.
One of the easiest and most effective methods to try is an external website containing a login screen, with the company logo. Send out emails to employees from an external account, claiming to be the sysadmin, saying you've got a new staff portal. Every time a user logs in, have it direct to a page explaining what they just fell for and how they can recognise it in future. Include your phone number and email address in case the user wants to know more. Every time a user calls you up to ask if it's safe, or to report it as a security issue, tell them they did the right thing and make sure their line manager is aware of their success.
Next one to try is a more direct one. Send out an email (again, from an external mailbox) saying that the database is having problems and you've got to re-enter everyone's passwords. Ask them to send their passwords to a "secure password update mailbox", and wait. Every time someone sends a password, explain to them that they just fell for a phishing attack. Downside of this attack is that you'll have to reset a lot of people's passwords!
Just one word of advice: get authorisation to do this before you start the project! ;)