We have this happen with Alt-N Mdeamon and Outlook. In this case it will only archive items according to when the cache was built and not when the email was originally created i.e. if you rebuild the cache today, and then you set your archive to archive anything over 1 month old, it will not archive a single thing until 1 month passes. Then it should sort itself out and just leave you 1 month of emails in the current directories. It seems to build the directory structure straight away regardless of this.
I do know that if you manually move the emails to the archive that this works.
And, I'm sorry if this doesn't apply to you in anyway!