Views SQL-query slow with big dataset and exposed filters
Try denormalising the database by storing the relevant node objects in a single caching table. You can model your database schema on that of the core caching tables. That should speed up the query by reducing the amount of joins. Also, put indexes on any columns used in where clauses. If you insert/update rows in your caching table on update/insert of nodes using hook_nodeapi, your caching table should remain fresh. You could then either replace the view with a db_query in a custom module, or you could expose your table to views.

I haven't tried it, but you may be able to achieve this using the D6 object cache module.