Had this recently at a customer's - the server would send emails if you added a user to a site, or if you registered for an alert - you'd get the email saying the alert was activated. But when someone added an item to the list, you didnt get the email for the alert.
Looking in the Timer Job Status list in central admin showed that we had two front end servers, and on one of them the "Immediate Alerts" job was always on "failed". After much research and head banging, a collegue of mine suggested I look into the relay settings of the SMTP server.
When I opened the relay settings I found to my surprise that the IP addresses that were configured to allow relay did not include the IP address for one of the front end servers. Adding that IP address resolved the problem.
Now the alerts are working, but for some reason the " Send e-mail when ownership is assigned" on a task list is not working. Wish I knew how to fix that...