So you have it checked in Site Settings > Security
Require Approval Before New Users Can Sign In?
And you approve the user from the ManageUsers.aspx page?
and nowhere in web.config nor user.config do you have this setting which would disable it?
<add key="NotifyUsersOnAccountApproval" value="false" />
If those things are all true then I am just as puzzled as you unless your smtp server is only relaying to specific domains or is otherwise configured to not send certain emails.
Best,
Joe