The problem is extremely convenient given that it's a breeze to
reproduce: All I have to do is create a reminder and set the date to 5
minutes from now and it won't display (0 minute "time limit", so it
should appear at the requested time).

I've tried /cleanreminders, /firstrun and /resetfolders to no
significant avail. A reminder is typically displayed the first time
after running /cleanreminders, but then the behaviour becomes less
rewarding, with the return of the above described problem.

Previously we used Outlook 98 and had similar problems but that usually
included an error message stating "Operation Failed" shortly after
opening OL98. The problem here was recurring reminders and I usually
solved it by deleting and recreating them, and subsequently running
/cleanreminders.

The closest I came to the problem on support.microsoft.com is probably
this link:
http://support.microsoft.com/default.aspx?scid=kb;en-us;327547

I also found the following article:
http://support.microsoft.com/kb/178698/EN-US/

Any ideas beyond this? I'll mention this to the Exchange Server Admins
tomorrow (20:30 here).