Add the field “modified date” in the folders that are not archiving and see what that date is. One maddening thing I found out working with a case like yours is archiving actually takes place based on last modified date, not receive or sent date. This is a “feature” with outlook, not a “problem”. One user whose mail would not archive I found out had recently set up his outlook to use cached mode. Well guess what? Turning on cached mode changes the modified date to the date it was cached. So although he had lots of mail that was older than the auto-archive settings, none of it would archive because the modified date of all of it was too recent! And it changes it on the server side so no matter what computer he went to he had the same problem! Oh and there is no way to change the modified date back either.
Update from hoodbu: I got this to work. Indeed, old items that are moved (such as due to creating a new folder once you realize that your Inbox is growing big) are considered modified. Hence they don’t get Archived. The trick is to reduce X in the ‘archive items older than X days’ field.