Are you using always-up-to-date mode(IMAP IDLE), sync internal(e.g 20 mins) or manual sync ? The messages will be moved/deleted in the next sync, if in always-up-to-date mode they will be moved right away but will only appear as new if the new folder is favorite, if not they will appear next time you visit the folder or do a full sync.