Seems like I finally got the permissions right!
To search all users by email I enabled these permissions for my Api-User:
- moodle/user:viewdetails
- moodle/user:viewhiddendetails
- moodle/user:viewalldetails
- moodle/site:viewuseridentity
To enrol users to course I enabled the permission moodle/role:assign and set the role-specific assignments through /admin/roles/allow.php?mode=assign
The permission jungle is pretty overwhelming at first sight. Feel free to comment if you have any tips for permission management.