Perhaps you could try the following:
(1) Check preceeding rules for errors. Pegasus seems to skip the rest of the rule set if a rule is malformed. This is most likely to happen if you edit the rule file directly, but I think it is possible to introduce such errors using the built-in rule editor too.
(2) If you have rules with "Download" action then check if any of them might match messages that should be deleted. From what I think I know, Pegasus will do the actual download or deletion after exiting from the rule set - not while still running the message tests. Unexpected things might happen if rules with opposing actions match.
(3) Check any rules with "Goto Label", "Exit this rule set", etc actions so you don't accidentally bypass the "Delete" actions.
(4) If everything else fails, then build a new rule set with just one of the "Delete rules". Attach it to your POP3 definition and verify that it works. Finally add one rule at a time, all the while making sure that rules still work.
HTH
Erik