After some playing around I realised it’s really simple with SQL, provided you have full database access.
I’m posting these as SELECT queries because you should run them that way first to check you have the right users before you DELETE. Anyone who doesn’t understand this should not try it!
SELECT * FROM wp_users WHERE ID NOT IN (SELECT user_id FROM WP_usermeta WHERE meta_key = 'wp_##_capabilities')
Your tables may have different prefixes.
You can use a similar query to delete records from other tables when they no longer have a user in users.