Even indexes will not fix the search as it is, the whole of the search code needs re-writing to be optimised for the database in use, and if possible freetext indexing should be used. There are mods around that do one or both of those things.
There is no tried and tested index additions, since they really depend on how the majority of users use the forum, the only way to find out is to run the sql profiling tools while your forum is being used and then sql will tell you if you need to create/change your indexes.