I once faced an issue with email notifications for alerts on list/library not being sent.
The cause of the problem could be one of the two cases: Either the server has been upgraded from WSS 2.0 to WSS 3.0 or insufficient rights are given to the person/group for which alert is being set to. This is apparently a bug as suggested by Microsoft in the following article:
My case was permissions related. We managed to solve the problem by going through the following steps:
1. Executed a couple of stsadm commands to enable the alert and set the time of the alert job
stsadm.exe -o setproperty -propertyname alerts-enabled -propertyvalue true -url http://problemsiteURL
stsadm.exe -o setproperty -propertyname job-immediate-alerts -propertyvalue "every 5 minutes" -url http://problemsiteURL
2. Reset Windows Timer Services.
3. Set the person/group for whom alert is being set to contribute permissions to the list/library for which alert is to be set.
In other cases, even after following the above steps if emails do not start, it might be due to upgrade, and difference of site urls in content database and actual web application. For this one of the two steps given in the MS article above needs to be taken.