We archive and shortcut all emails over 90 days old from the users Inbox, Sent Items, user Defined Folders and Process Sub Folders. We do not Remove Message Body when shortcutting so Outlook's preview pane still displays the email OK. We get about 70% reduction in storage requirements using this policy.

The archive and shortcut tasks run everyday only stopping for backups.

Run some test archive and shortcut tasks to find out how long it takes. Learn to use the Analysis Task in EmailXtract for Exchange to set reasonable expectations on how long the entire archive process is likely to take.

Thanks Andrew, I've appreciated your contribute.
I was able actually to do some analysis work and it seems our issue is that we are not moving out from Exchange as much data as expected.
This is caused by 2 facts:
1) emails are growing exponancially, so the big chunk is newer than 90 days
2) our customers have been forced through the mailbox limits to archive or delete old stuff on a regular basis, so there is not a lot stored in the past
Consequently we may need to reset the shortcutting at different levels: a bit more recent that 90 days, all the big attachments, all the pictures, and so on....
So that's the reason I'm still looking for ideas...

Cheers
Francesco