Are you using IMAP or POP? I haven't seen a problem with IMAP but then again I always want it deleted from the server (it's IMAP after all). I don't think I've used POP in almost a decade, you might try IMAP if the server allows it.