I see that searching all wikis can be a huge performance issue.
As an alternative I would suggest to add interwiki links to the search result page that simply links to search result pages of other wikis without issuing a query on these wikis.

ok, thanks!

Thanks demon!

Thanks, Sjoerddebruin. That script is pretty useful!
However, my suggestion is to add this feature to wikipedia.org so all users could use it by default.