Having them setup as POP is the problem. You need to setup those Outlook accounts as "IMAP" instead of POP3. Reason being, is that POP will download the mail to your local system and even though you obviously have Outlook configured to "leave a copy on the Server"...when you delete the mail from Outlook you are only deleting it from the local machine.
Configure the Outlook accounts as IMAP and when you delete messages they will actually be deleted from the Server -- thus deleting them from your IPhone as well.