Thanks. We ended up logging a ticket with Microsoft and an engineer from Costa Rica helped me out. We never did really figure out what was wrong, but they started to work again when I switched to cached mode. They still don't work in on-line mode, but he told me that I would be better off keeping it in cached mode anyway. He thinks my e-mail profile may be corrupted somehow, but I do see the Toast alerts and envelope icon.

I found it interesting to find out why they are called TOAST Alerts. I thought this was some high-tech Microsoft acronym, but he told me that they are called that because the alerts pop-up just like a toaster.