When you have a few thousand entries and use post_type in combination with meta values, the MySQL query starts running very, very slowly because it seems to do a full table scan on the wp_postmeta table. The most direct solution is to add an index on the wp_postmeta table to avoid the full scan.
This is the SQL to add the index:
ALTER TABLE `wp_postmeta` ADD INDEX `key_value` (`meta_key`(20), `meta_value`(20)) USING BTREE;
The speed improvement was somewhere around 100x. I needed the first twenty characters of each field — you could alter it to be more or less.