Settings API in Multisite – Missing update message

For network option pages the correct form action URL is:

wp-admin/network/edit.php?action=your_option_name

Then you have to register a callback:

add_action( 
    'network_admin_edit_your_option_name', 
    'your_save_network_options_function' 
);

In that callback function inspect the $_POST data, prepare the values, then save them:

update_site_option( $this->option_name, $this->option_values );

And then you have to create the redirect without further help:

// redirect to settings page in network
wp_redirect(
    add_query_arg(
        array( 'page' => 'your_options_page_slug', 'updated' => 'true' ),
        (is_multisite() ? network_admin_url( 'admin.php' ) : admin_url( 'admin.php' ))
    )
);
exit;

On the options page check $_GET['updated'], and add an admin notice if you found that parameter.