I think that a big search button in an obvious place (next to submit reply isn't a bad location) with instructions on its use would be great. The other thing that would help encourage the knuckleheads to use it would be some kind of "punishment" or standard message that comes about from posting something that has been asked and answered multiple times.
I try and post a reply to those repetitive posts to the affect of use the search function and save the pros and server time and heartache answering stuff that has been asked and answered many times before. I usually get an angry sarcastic shot back from the offender.
Mods should also delete and remove post counts from people who post anything just to bump their count....like, I know this doesn't have anything to do with the thread, but... This is just as annoying, granted sometimes you get off the original post but blatent post whoring makes me mad.