It sounds like you’re already on the right track, adding additional indexes and tweaking the query. I’ve found MySQL’s EXPLAIN syntax to be helpful, giving me a good sense of where in the query things might be going awry.
From a high-level, it appears that the query has a lot of joined tables, LIKE comparisons (with wildcards), and OR comparators, all of which are symptomatic of potentially less-than-performant queries. I’d ensure that each of those columns are indexed properly (especially those that perhaps aren’t normally queried), and see if you’ve missed anything there.
Overall database size can be a factor in some environments; at one point, a client site was complaining about slow performance (not just search) and we discovered that indexes were choking on the fact that about 20% of the database was made up of post revisions (this was a daily news site, so revisions on a post from six months ago wasn’t really relevant). Revision Strike was born out of that need, and had a huge impact on general – as well as search – site performance.
Another option to consider is something based on a more dedicated search technology. ElasticPress (full disclosure: I work for 10up, the maintainer of ElasticPress) ties Elasticsearch into WordPress queries, significantly reducing the load on your web server while making it possible to do more complicated searches (like you appear to be doing with your search plugins).