Checking if meta values exist

You can use get_posts() (or the WP_Query object) to query all posts which match the post meta you want to save. You will need to specify the post status (i.e. which statuses are you willing to ignore). Below is the untested code to this.

(For completeness I’ve left in arguments which could be omitted because they are given their default value). I also exlude the current post, in case the post is being updated – since otherwise that post will be returned and we’ll think a post already exists with that meta data.

//Collect the terms
//I'm assuming that each of the values are strings. 
$meta_terms = $_POST['post_terms'];
$meta_taxs = $_POST['post_taxonomies'];
$meta_types = $_POST['post_types'];

//Query post type 'products' to check for posts whose meta values match the POSTed ones
$args = array(
  'post__not_in'=> array($id),
  'post_type' => 'product',
  'post_status' => array('publish','pending','draft','future','private'),
  'meta_query' => array(
      'relation' => 'AND',
      array(
        'key' => 'post_terms',
        'value' => $meta_terms,
        'compare' => '='
      ),
      array(
        'key' => 'post_taxonomies',
        'value' => $meta_taxs,
        'compare' => '='
      ),
      array(
        'key' => 'post_types',
        'value' => $meta_types
        'compare' => '='
      )
  )
);
$existingMeta = get_posts( $args );

if(empty($existingMeta)){
    //Go ahead and save meta data
}else{
    //Revert post back to draft status as shown in linked answer below.
}

Side remarks

The ‘post_terms’ etc seem quite generic. I would give them more descriptive and unique names – event more so if being used as key in the post meta table. Also, to avoid conflict you might want to send the data inside an array with a unique name: i.e.

<input type="text" name="myplugin[post_terms]" value=""/>

Then retrieve the data as $_POST['myplugin']['post_terms'] rather than $_POST['post_terms']. You can be reasonably sure that any data inside $_POST['myplugin'] has been over-written by another plug-in. Also you must use nonces to help verify source / intention.

Preventing the post from publishing

You can’t prevent a post from being published (unless you use jQuery). However, immediately after a post is published, you can perform a check and, if desired, revert it back to draft status: See my solution to this related question.

Displaying a Custom message

In the linked solution, if a post had been reverted back to draft, I set the message variable to ’10’ so that the draft message is shown: ‘Draft updated….‘:

add_filter('redirect_post_location','my_redirect_location',10,2);
function my_redirect_location($location,$post_id){
    //If post was published...
    if (isset($_POST['publish'])){
        //obtain current post status
        $status = get_post_status( $post_id );

        //The post was 'published', but if it is still a draft, display draft message (10).
        if($status=='draft')
            $location = add_query_arg('message', 10, $location)
    }

    return $location;
}

You can however specify your own message. The 10 refers to an array key where each value is a message. 0 is blank, with 1-9 being the default messages (post published, updated, etc.)

(This is untested) but you can add your own messages to this array:

add_filter('post_updated_messages', 'my_custom_messages');
function my_custom_messages($messages){
    //$message is an array of arrays. 
    //$message['post_type'] is an array of messages for post type 'post_type'
    //It is a non-assocative array. Value for 0 is blank. Keys 1-9 hold the default messages
   
    //Add a custom message to key 21 for post type 'my_post_type'
    $messages['my_post_type'][21] = 'Looks like you tried publishing, but something went wrong';

  return $messages
}

Then you can set the message to 21 rather than 10 as demonstrated above.