I think the Exchange model for handling Messages/Attachments/Single Instance Storage (SIS) has reached its limits.
I think Messages should be stored in one place -- and Attachments stored someplace else other than the Mailbox Stores. (Attachments should be stored in a database or a file-system share or a Sharepoint library, if that scales sufficiently.)
In this way, the moment a message is received from an outside party, or a message is generated internally, the attachment would stored in a SIS within the organization. Ideally you would like to see MIME still work as-expected, so that when the message is sent from internal to external, the attachment goes along for the ride.
Our company uses a third-party archiving package -- but it really would be unneccessary if Exchange handled Single-Instance-Storage of attachments, efficiently from the moment the mail is generated.