I've recently done this at my place and it's very handy. All it requires is a small edit to MessageIndex.template and Display.template, plus I also put one in the info center.
I used the filter.gif to link to advanced search as well, so now I have full search options at the base of the page no matter where I am in the forum. Since it's so easy to do and so convenient I think it's worth considering as a standard feature.
Its certainly an idea. I imagine some people would question the need for a search box at both the top and bottom of the site though when there is an option to go back to the top of the page.
It would probably end up getting used as much as the jumpto box does. (rarely).
Or in my case, not ever.
Ah, well I run custom themes that don't have a search window at the head of the page, and using the windows is more convenient than going through the menu button. It may be worth someone writing a mod for it.