Could you tell us how do you configure "clean up old items"? Clean up with AutoArchive or Clean up manually?
If you are using AutoArchive, please have a check whether the "Do not archive items in this folder" is unchecked:
If you try to clean up manually, you also need to check the settings below:
Yes, the Outlook archive function only handle with emails which downloaded to local computer. It will not handle old emails which doesn't downloaded to local computer. For those old email, you could use server side archive function: In-Place Archiving in Exchange Server