The problem was that the nc_hidden met property did not exist if it was not checked so there was essentially no value to query against.
I swapped nc_hidden from a checkbox to a select and updated my query as required. The working query is now as follows:
$query_args = array(
'posts_per_page' => '1',
'orderby' => 'rand',
'post_type' => 'nc_property',
'meta_query' => array(
array(
'key' => 'nc_featured',
'value' => 'on',
'compare' => '='
),
array(
'key' => 'nc_hidden',
'value' => 'Visible',
'compare' => '='
)
)
);
Thanks @Milo for pointing me in the right direction.