I was reading Jeff's post on Coding Horror about naughty filters (and I more or less agree - you can't fix a social problem with technology). Towards the end he mentions Yahoo Mail, which brought to mind a nice feature they added recently to search:
Now, when you do a keyword search, it presents a small summary in the sidebar about the matching mail's properties (like dates / from / to / folder / attachments / etc). This is a really, really nice, easy and discoverable way to do advanced searching. Compare this with the two usual methods: special "keyword expressions" which no-one can remember (or knows about for that matter) or the "advanced search screen" which has some many fields that you can't count them on your fingers and your toes combined. Yes, it needs a little extra work from the backend (grouping the resultset via different criterias), but in my opinion this is a very good and useful way to augment search.