It was actually much easier than I originally thought – just doing a WP_User_Query
for a meta value (meta arrays are supported as well, like for the other query classes).
public function on_deactivate()
{
$meta_key = 'tools_page_tsi_per_page';
$query = new WP_User_Query( array( 'meta_key' => $meta_key ) );
if ( empty( $query->results ) )
return;
foreach ( wp_list_pluck( $query->results, 'ID' ) as $user_id )
delete_user_meta( $user_id, $meta_key );
}