As with VBA, the code modules would travel with the document. Unlike VBA, the same Arcmap singleton used in Add-ins would be provided. This would make it easy to migrate .NET code from the document to the add-in at a later time. I don't think storing code in mxt files is needed - make people use add-ins if they want to share customizations.
Basically, it would be an add-in that is stored within the document, is edited with something like sharpdevelop, and compiled with CodeDom.
Administrators should be able to configure a machine to either allow,alert, or deny running add-ins that are stored in documents.