Taxonomy Tag Conditionals

If you want to use an entirely different template, you could filter 404_template and check query vars for a specific taxonomy:

function wpa83050_404_template( $template="" ){
    global $wp_query;
    if( isset( $wp_query->query_vars['product_cat'] ) )
        $template = locate_template( array( "product_taxonomy-no.php", $template ), false );
    return $template;
}
add_filter( '404_template', 'wpa83050_404_template' );

You could also just put logic similar to the above in your 404 template and use that single template for all 404s, check $wp_query for what query vars are set and print some text accordingly. add var_dump( $wp_query ); to your template to see what query vars get set under different conditions.