Deleted messages being permanently deleted when set not to

So I've been having this problem since I got my iPhone a few weeks ago. I use two IMAP accounts (neither one of them are Gmail) and I like to keep all of my deleted messages so that I can go back and search for stuff that I need later on. I have the option for when to permanently delete trash messages set to never in both Mail.app on my Macbook and on my iPhone. For some reason it is still deleting all messages more than a week old. Does anyone else have this problem?