"I have the feeling that this will require a custom SQL query"
So do I... But actually, here's two ways to do it.
1. This is similar to what I use on my site for my plugins Page; it uses query_posts() to pull in the category, then tests custom key/value:
<?php
$catid = ''; // set to category ID #
$customkey = ''; // set to your custom key
$customvalue = ''; // set to custom value
query_posts("cat=$catid&showposts=-1");
while(have_posts()) : the_post();
$value = post_custom("$customkey");
if($customvalue == $value) : $more = 0;
?>
~ Your "Loop" template tags and whatnot go here ~
<?php endif; endwhile; ?>
2. The custom SQL query you were expecting:
<?php
$catid = ''; // set to category ID #
$customkey = ''; // set to your custom key
$customvalue = ''; // set to custom value
global $wpdb;
$my_posts = $wpdb->get_results("SELECT * FROM $wpdb->posts, $wpdb->post2cat, $wpdb->postmeta WHERE ID = $wpdb->post2cat.post_id AND ID = $wpdb->postmeta.post_id AND $wpdb->post2cat.category_id = '$catid' AND meta_key = '$customkey' AND meta_value = '$customvalue' ORDER BY post_date DESC");
foreach($my_posts as $post) : setup_postdata($post);
?>
~ Your "Loop" template tags and whatnot go here ~
<?php endforeach; ?>
For either option, just make sure to set the correct values for the three variables at the top of each code block: $catid, $customkey and $customvalue.