I know you checked your settings, but test this just in case.
The settings in Tools::Options:

references Tab::Email Options::Advanced Email Options?
1. Is there a check mark on "display a new mail alert"?
2. If below that you click on the button "desktop alert settings", and play around with those settings (for example as silly as it sounds - make sure the transparency is not set to "clear"),
does it work when you click to preview it?
If that does not work, I would suggest backing up your outlook.pst files that you use along with exporting a backup of your contacts and then of your rules. After that, try reinstalling Outlook. That might be easier than trying to find the glitch that is causing your problem.
Oh one important thing - keep in mind that the desktop alert only works for the default inbox, and I am not sure it works with email addresses such as hotmail and the like. Just like the outlook rules, I believe the desktop alert only applies to regular pop addresses and not to html-like services. Mine works with my google email and my other email addresses from school and from my IP provider, but it does not work with hotmail.