Acutally, later builds of UBB have the search box prominently about; I think that this would take little time to do as you suggest.

As for forum indexes, sure, its good, but it should be bigger, shinier and cry "SEARCH IS HERE".