Few months back I too faced same kind of issues, where the newly added users in the Active Directory were not getting the notification emails. It was because the users in the active directory should be added in the Site Collection also, so that the workflow can fetch the email ID of the users and send mail. To bring in all the users from Active Directory to your web application, you have to configure the User Profile Synchronization in the Central Administrator.
Please configure the below in the sharepoint server,
1.Configure User profile Synchronization.
REF:
http://technet.microsoft.com/en-us/library/ee721049(v=office.14).aspx
1.1 Once after configuring, you need to set up a Timer Job which keeps the SharePoint 2010 Server in sync with the Active Directory, Schedule User profile Synchronization.
REF:
http://technet.microsoft.com/en-us/library/ee890103(v=office.14).aspx
Once after the above configuration, we can also create a Windows task Scheduler to run the Synchronization code in a daily basis (same like #2), to do that please follow the below link.
REF :
http://gallery.technet.microsoft.com/office/Sync-user-information-in-d1b9aed5