Hi Brett,
Yep.... have had the same problem for a couple of weeks now. So far the only info I've come up with was from Yahoo Answers. Seems like an awful lot of people are having the same problem. Like you, others have tried everthing with no success. Doesn't matter which version you have either. One poster said "It seems to be affecting only some accounts, as others can sign in on same computer and receive their alerts.... I sent Yahoo a message about this a week ago, and got the generic response that my question was very important to them, but their normal response time would take longer than the usual 24 hours. ... No response yet. ... I'm sure they are aware of the problem by now, but thus far no fix."
Ha! You know what that means! Hold your hand on your a** and wait!
I did see an answer from someone using Foxfire, but I can't seem to find it again for you. They used some kind of new plug in for Yahoo mail alerts. Said it worked fine and they gave a link in their answer. Another poster said they tried it and it solved the problem for now.
You can search over there at Yahoo Answers, if you like. Just type "Yahoo messenger email alerts not working" in the search box.