Cannot save Checkbox meta box value from a Custom Post Type

In my opinion the problem is the way you operate the checkbox.
As the checkbox value, you set the value read from the database, which is sometimes an empty string.

When you send an unchecked checkbox, there is no $_POST['chkClientShow'] key and an empty string is saved to the database.
Then the empty string is set as the checkbox value. From now, the custom field _clients_show always will be an empty string.

The following code should work

function infotravel_clients_visible_metabox( $post ) {
    wp_nonce_field( 'clients_show', 'clients_show_nonce' );
    $value = get_post_meta( $post->ID, '_clients_show', true );
    $is_checked = ($value == 1) ? 'checked' : '';
    ?>
    <input type="checkbox" id="chkClientShow" name="chkClientShow" value="1" <?php echo $is_checked; ?>/>
    <label for="chkClientShow">Show this client on Clients page</label>
    <?php
}

function infotravel_save_clients_meta( $post_id ) 
{
    //
    // ...
    //

    $visible = isset( $_POST['chkClientShow'] ) && $_POST['chkClientShow'] == 1;
    $visible = (int)$visible;
    update_post_meta( $post_id,  '_clients_show', $visible );

    //
    // ...
    //
}