Wait 30 minutes after creating a rule before you test it. If you test immediately after you create the rule, you might get inconsistent behavior. If are using Exchange Server and have multiple Exchange servers, it might take even longer for all the servers to receive the rule.
Reference: Microsoft TechNet