Group Custom post type in a page by its taxomony tag

If I follow your question correctly you could use a nested query loop, that is looping through your taxonomy terms and then doing a WP_Query loop for each one.

There is a more complicated approach using custom SQL and a filter but the following example is what I would go for:

$terms = get_terms("locations");
$count = count($terms);
if ( $count > 0 ){
    foreach ( $terms as $term ) {
        echo '<h2>' . $term->name . '</h2>';
        echo '<ul>';
        $loop = new WP_Query( array( 
            'post_type' => 'vacationrental',
            'post_per_page' => 100,
            'orderby' => 'date',
            'order' => 'ASC',
            'tax_query' => array(
                array(
                    'taxonomy' => 'locations',
                    'field' => 'id',
                    'terms' => $term->term_id
                )
            )
        ));
        // the loop
        while ($loop->have_posts()) : $loop->the_post();
            // do loop content
            echo '<li>' . get_the_title() . '</li>';
        endwhile;
        // reset $post so that the rest of the template is in the original context
        wp_reset_postdata();
        echo '</ul>';
    }
}