Just to be clear, you're saying that in your recent test, you received
alerts when expected, but you have other users  who are not receiving their
alerts?

We haven't received alerts  since 10/31/2009. When I perform my tests now, no
alerts are being received by any of my users, including myself.

I would check these three things:

In Central Administration of Sharepoint, click on the Operations tab and go to
Timer Job Status. Look and see if the Immediate Alert jobs are running; you can
see the last time they ran and whether or not they are successful(this is only
good for immediate alerts  obviously, I'm not sure what triggers the time based
types of alerts)

Check to make sure the Windows sharepoint  Service Timer is running on the
sharepoint server. If it is running, a restart of the service may help.

Make sure that the account the Windows SharePoint Service Timer is logging on as
has not changed passwords.

For us, it was the last item that made the difference. The account that the
service was running as had been changed and no one caught that it broke the
alerts for several weeks.

In addition to that list, you might check to see if any service packs or
updates were applied around that time.

Also check your mail server  logs to see if the messages aren't getting
there, or are sitting and never being sent.

If there still isn't a clear cause, then check your SharePoint logs (in
12/Logs) right after doing something that should send an immediate alert.
You may find a relevant error message there. Check the Windows event log as
well.

We experienced this issue  and I found this blog post

http://eddyblanco.com/blog/?p=39

By running the suggested STSADM commands, this repaired our alerts  issue.

1. stsadm -o setproperty -propertyname alerts-enabled -propertyvalue false
-url
2. stsadm -o setproperty -propertyname alerts-enabled -propertyvalue true -url
3. stsadm -o setproperty -propertyname job-immediate-alerts -propertyvalue
"every 5 minutes" -url
Also if you are exceeding the maximum size of a SharePoint discretionary access
control list (DACL) of 64 KB or approximately 1,820 access control entries
(ACEs) it can have a negative effect on search and alerts.

http://support.microsoft.com/kb/953132