I would compare everything in the new users’ profiles in AD to known working profiles to see if you can find the differences. Also do you use a third party filtering service such as Message Labs? Have they sent emails to external addresses successfully? I know Message Labs has an address registry which blocks new users until they send an external email which then registers that email address as valid.
what you could also check on their account is what email address is assigned and primary. go into active directory users and computers. open the account. go to the EMAIL ADDRESSES tab. This will show all email addresses assigned to that account. It could be possible that when you created the account that it only assigned the X400 address and not your normal firstname.lastname@example.org address. This is how we block our internal users from getting email from outside.
let me know if that helps!