Hey All,
This one likely doesn't actually have anything to do with your email setup, since the test emails are sending fine. I would start looking at Active Directory as that is the next problem area. Basically the Test Emails use the full SMTP functionality, so you have proved that works, but now the next step is to get email/user information from AD, which is likely where your issues lie.
First, I would make sure that all of the working and non-working users are in the same Domain. For example, if you had Domain A and Domain B, I would make sure that you have working users in both domains.
Next, go through Section III. Email Message Related Issues of this article:
community.dynamics.com/.../workflow-notification-email-troubleshooting
Specifically, I would check to make sure all users have email addresses setup on their AD card. You can also compare the AD card from a working user against a non-working user to see if there are any fields (like Full Name) that are missing.
Past this you can run NetMon/Wireshark traces and review it to see if LDAP traffic is working correctly, along with reviewing Workflow Logs and Event Viewer. Instructions for all of these can be found in the troubleshooting guide linked above.
Hopefully something here will get you on your way!