Mail not deleting messages from server

Hi I'm using a pop mail account on multiple devices. Under advanced options I've set my iPhone to remove a mail from the server as soon as it's been moved from the inbox (I assume deleting qualifies as moving), yet when I delete a message from the iPhone, it still shows up on my mac when I get mail. I tried setting up mail on iCloud to see if synching it with that would fix the problem, but no go. Has anyone experienced this or found a fix? It's somewhat annoying. Best regards: Malthe.