I too have been having this issue, in my case with Outlook Vista. None of the above advice fixed my problem. However, upon starting up Outlook this morning...the long-gone reminder box popped up (with about 25 past due reminders in it)!
I quickly thought back to anything I had done differently in the past 24 hours, so here's a possible solution:
In my case, I had opened up an old archive PST file using New/Outlook Data File in order to look for an old archived message. This took a while because Outlook Vista wanted to index the entire 500MB file. I allowed it to do so for a while, came back to the 'puter and made my search once indexing was done. Some time later, I closed the older PST file, closed Outlook and didn't re-open it until this morning...and suddenly reminders are working again.
Could be very oddball just for me and my system, but worth a try if none of the above advice has worked for you. Try opening up another PST file if you have one and allow Outlook Vista to index it; close and re-open; cross your fingers.
P.S. I did ensure there were no Windows Updates overnight. There weren't.