Is Outlook in this situation talking to Exchange or an IMAP server? If Exchange, what version? (also what version of Outlook?) Rules handling and the quirks Outlook has varies based on this.

My initial guess is that this is an Exchange environment. If it's new enough, try logging on to the web version of Outlook and check the rule there, make sure it's actually saved on the server the way your client sees it.

If you can't find rules in OWA, there is a good chance the Exchange server is pretty old.