We followed the instructions here:
EnableSharingAddin - ZimbraWiki
It works, but then when the user closes and reopens outlook, the key is reset.
It appears the act of closing outlook disables the add-in.
Support did mention that my problem may be related to Bug 18408 but unlike their test case, the crash occurs on all e-mail addresses, including simple ones like email@example.com.