Understand, this doesn't answer the question though. What users who should not be getting the emails are and what roles or privilege level are they part of? Are you sure none of them have any other roles assigned to them?
If you look at the first "INFORMATION" point on this documentation page, it states:
"The system sends all workflow emails to users who have the Manage workflow permission, regardless of the settings on the Security tab of a custom workflow step."
So if a user is part of a different role which has the "Manage workflow" permission, they will get emails no matter what. Unfortunately, this is can even be an editor of sorts.