Some parts of user education are tough; notably, viewing malicious websites. All Windows web browsers have vulnerabilities and websites posing as legitimate, even innocent, will compromise them. Google spamming sucks in users like a bug zapper. It takes a whole new level of education to teach users to avoid these websites without even visiting them.

I constantly try to share my URL and domain name paranoia with my coworkers so they can avoid unsavory sites. Avoid domain names with:
More than one dash
Stupid letter replacement (z for s, 1 for l, etc)
Overly long
Random characters
Prefix or suffix on a popular domain name (ie: linksysinfo.com)
Wrong top level domain, and NEVER .biz or .info
etc
etc

And teaching them to preview the two line Google page excerpt. Avoid:
Keyword repeated 6 times among random words.
"Best deals on ____. Find all your ____."
"Coming Soon", "This Domain is available", etc.
etc
etc

This leads back to my "trusted sites" idea. Just like the pre-search-engine days when people posted link directories, there should be directories of trusted sites. Maybe a web of trust, tightly controlled by the members of the web (not infinitely expanding like the PGP key model). Display only known legitimate sites, accept link requests from the outside, post those links after through review, swiftly remove sites turned bad.

Think of how easy it would be to find trustworthy product reviews, legitimate online retailers, non-popup'ed lyrics sites, REAL information. Yes, it's labor intensive, but that's how I do things. Maybe there's a way to make this work.