What's the best tool to find and replace regular expressions over multiple files?

Perl.

Seriously, it makes sysadmin stuff so much easier. Here's an example:

perl -pi -e 's/something/somethingelse/g' *.log

sed is quick and easy:

sed -e "s/pattern/result/" <file list>

You can also join it with find:

find <other find args> -exec sed -e "s/pattern/result/" "{}" ";"

I've written a free command line tool for Windows to do this. It's called rxrepl, it supports unicode and file search. Some may find it useful.