Exclude from search all custom posts which are NOT in a taxonomy term

After reading your revised question it was easier to comprehend what you are trying to do. My new solution looks like the thing you wanted to do in the first place: it just excludes all posts which are of your custom type but don’t have the “yes”-term associated with it:

$custom_query = array();
$custom_query['post_type'] = 'any';

// first, query all the posts of your custom type
// that don't have the "yes"-term:
$tmp_wp_query = new WP_Query(array(
    'posts_per_page' => -1,
    'fields' => 'ids',
    'post_type' => 'your-post-type',
    'tax_query' => array(array(
        'taxonomy' => 'tax-whatever', 'terms' => array('term-whatever'),
        'field' => 'slug', 'operator' => 'NOT IN'
    ))
));

if(!empty($tmp_wp_query->posts)) {
    // Exclude the "yes"-less posts from the actual post query
    $custom_query['post__not_in'] = $tmp_wp_query->posts;
}

// now proceed with your original code and execute the definitive query
$args = array_merge( $wp_query->query, $custom_query );
query_posts( $args );

$search = new WP_Query($search_query);

The only downside is, that there are now two queries to run. But the first query is relatively light-weight so the performance-loss should not be that huge.