In a partial sandbox I am calling Messaging.sendEmail through an @InvocableMethod through a Flow, and emails are not going out for a non-admin profile. There are no errors anywhere and even debugging Messaging.SendEmailResult.isSuccess() shows true. The arrangement works fine for an admin user.
I haven't tried with other profiles (or in other sandboxes or in Production) but I have verified that every occurrence of the word "email" throughout this one profile is met with a ticked box. Email deliverability is set to All Emails (should be obvious by now, but just being explicit) and the code is setting templateId, whatId, and targetObjectId. Dead basic. The profile in question has access to the template and the related records in whatId and targetObjectId.
FWIW I have also tried with toAddresses in the email with no luck.