When I need to delete a user, I delete their entry from the users table and flag any associated identities for deletion.
Do I need to do anything with contacts, contactgroups, or any other table?
Or perhaps cleandb.sh will take care of it later?
If you delete a user in the database from the users table everything that goes with that user should be removed automatically. You can also use deluser.sh instead of deleting users in the db.