WP Query works outside a function, not inside a function

functions return an output. you don’t want to just echo it out.

try this as your function:

function mycoolquery() {
    $custom_taxterms = wp_get_object_terms( $post->ID, 'region', array('fields' => 'ids') );
// arguments
    $args = array(
        'post_type' => 'stay',
        'post_status' => 'publish',
        'posts_per_page' => 25, // you may edit this number
        'orderby' => 'rand',
        'tax_query' => array(
            array(
                'taxonomy' => 'region',
                'field' => 'id',
                'terms' => $custom_taxterms
            )
         ),
        'post__not_in' => array ($post->ID),
    );
    $related_items = new WP_Query( $args );
// loop over query
    if ($related_items->have_posts()) :
       $output="<ul>";
       while ( $related_items->have_posts() ) : $related_items->the_post();

            $output .= '<li><a href="'.the_permalink().'">'.the_title().'</a></li>';

        endwhile;
        $output .= '</ul>';
    endif;
    // Reset Post Data
    wp_reset_postdata();
    return $output;
}

then echo out the function where you want it:

echo mycoolquery();