I've been using Newsrover and it has a handy search feature built in - it allows you to choose where to search and I usually find what I need. Granted - I'm using news mainly for binairies and not searching for messages and stuff, but the search tool is very handy. It also has a separate mp3 search tool.

There are tons of features geared to searching non-binary related message forums too, and the autoscanning feature has tons of settings to tailor to exactly what you need. The demo allows you to do pretty much anything, but limits you to a download queue of no more than 50 items, so I just went ahead and spent the $29 for it.

I'm using Newsfeeds, and they have tons of servers. They have a server called "spamkiller" that pretty much does what it says. They have pretty much any server to fit whatever your need is.