Maybe a way to think about this is that the canonical url is based on the message-id, but then there's some way to distill even this down to a tinyurl or simple integer that would be stable in the face of full archive regenerations.
I'd suggest the reverse. Keep the canoncical archive URL short and sweet, and then use a URL redirection service to map message-id's to those URLs. It is the archiver's job to make it all work. For example, the canonical archive URL might stay exactly the way it is in pipermail. But the archival link embedded in the message would instead go to a redirection service.
http://mail.codeit.com/pipermail/zcommerce/2002-February/000523.html http://mail.codeit.com/msgid?002701c4eb3d$07170ca0$3142003e@ADSL
The one other thing I'd ike to revisit is integration with third party archival services. There are two obvious integration points; one is a button in the Mailman list admin user interface that says "archive with service X" not unlike the setting in Firefox that basically says "search with service X". The other integration point is the archival link discussed above. In which case it would be set to something like.
http://third-party-service/msgid?002701c4eb3d$07170ca0$3142003e@ADSL
Disclosure: I help run a third party archiving service, and this topic was discussed quite a bit previously. [1] Nonetheless it seems like a good time revisit given the current discussion about archive wishlists.
[1] http://www.mail-archive.com/mailman-developers@python.org/msg08772.html