Problem: Alerts on document libraries in MOSS work for portal administrators, but not for regular users. Regular users do receive the email notifying them that their alert has been set up.
Information: This was only happening on sites created with custom site definitions. Testing showed that the 'approval' permission could be added to the Members or other group of the site and alerts would then work for those users, but that is not a good solution for most environments.
Solution: Not a pretty one, but the best that Microsoft could come up with.
On all document libraries on custom site definition sites, break permissions inheritance and then re-inherit. It seems that something was broken in the site definition with regard to permissions. MS developer support is investigating, but the cause is still unknown.