You may have to hand-delete from Outlook. Verizon keeps copies of my Pop3 Verizon email on its My Verizon website. I have to periodically go to the My Verizon wireless account and delete them there by hand... even though they have been deleted from Gmail. Doesn't affect the Gmail, though. I check each time to be sure those emails I saved to Gmail folders are still there, and they are.
You might check your Gmail account's home page and search for Outlook-related info. There is a separate app to get your Gmail contacts imported from Outlook, so there may be a separate way to delete on both at the same time.