How to delete user from MU site when the user is removed from their site?

The function you are looking for is wpmu_delete_user($user->ID)

I wrote a small plugin to delete users across the whole network by role:

<?php
/**
 * Plugin Name: Regbox Delete multisite users
 * Plugin URI: http://www.regbox.se/delete-multisite-users
 * Description: Delete users by role across network
 * Version: 0.1
 * Author: Adam Rehal
 * Author URI: http://www.regbox.se
 * License: GPL2
 */
// Make admin menu item in Users

add_action('admin_menu', 'dmu_submenu_page');

function dmu_submenu_page() {
    add_submenu_page( 'users.php', 'Delete multisite users', 'Delete users', 'manage_options', 'delete-multisite-users', 'dmu_callback' );
}

function dmu_callback() {
    echo '<div class="wrap"><div id="icon-tools" class="icon32"></div>';
    echo '<h2>Delete multisite users</h2>';
    echo '<p>Delete users by role across network. This will delete all users with the selected role from the current site AND from the network</p>';
    echo '<p>Users with the same role on other sites will not be removed. You can also use the Count button to count the number of users with a specific role</p>';
    echo '</div>';

    // Get all roles
    global $wp_roles;
    $roles = $wp_roles->get_names();

    // Get all blogs
    $blog_list = get_blog_list( 0, 'all' ); ?>

    <form method="get" action="users.php?page=delete-multisite-users">
        <input type="hidden" name="page" value="delete-multisite-users">
        <input id="what-to-do" type="hidden" name="action" value="">

        <!--
        Select blog:
        <select name="blog">
        <?php
        foreach ($blog_list as $blog) { ?>
        <option value="<?php echo $blog['blog_id'];?>"><?php echo str_replace("https://wordpress.stackexchange.com/",'',$blog['path']);?></option>
        <?php }//end foreach ?>
        </select><br>
        -->

        Select Role:
        <select name="role">
        <?php foreach($roles as $role_value => $role_name) { ?>
           <option value="<?php echo $role_value;?>"><?php echo $role_name;?></option>
        <?php }//end foreach ?>
        </select>
        <input class="button button-secondary" onClick="javascript:document.getElementById('what-to-do').value="delete";" type="submit" value="Delete">
        <input class="button button-primary" onClick="javascript:document.getElementById('what-to-do').value="count";" type="submit" value="Count">
    </form>
    <?php
    // Needed to make use of wp_delete_user()
    require_once( ABSPATH . '/wp-admin/includes/user.php' );
    $data = new WP_User_Query( array( 'role' => $_GET['role']) );
    $userList = $data->get_results();
    $deleted = 0;
    $counted = 0;
    if($_GET['action'] == 'delete'){
        if($_GET['role'] != 'administrator'){
            foreach ($userList as $u) {
                if(wpmu_delete_user( $u->ID )){ $deleted++; }
            }
            echo "<p>" . $deleted . " user(s) deleted</p>";
        }else {
            echo "<p>Admin cannot be deleted</p>";
        }
    }
    if($_GET['action'] == 'count'){
        foreach ($userList as $u) {
            $counted++;
        }
        echo "<p>" . $counted . " " . $_GET['role'] . " user(s) on current site</p>";
    }
}