Are you using the clean up command (File > Tools) or auto archive feature to archive to a pst? That will remove the message from the mailbox online, but can take some time to sync the changes.
If you use the Archive button the ribbon, that just moves the messages to a new folder