Eu encontrei uma solução ...
Descobri que as credenciais adicionadas ao cmdkey foram mantidas, por meio do Azure Power Off, e foi apenas a Unidade de rede mapeada que estava desaparecendo.
Em vez de insistir em meu Serviço para se conectar ao Azure FileShare por uma Carta de Unidade de Rede Mapeada, alterei o código para acessar o compartilhamento de arquivos por seu endereço UNC.
\storageaccount.file.core.windows.net\MyFileShare
Com as credenciais adicionadas ao cmdkey store, nunca me pedem para me autenticar novamente ao navegar neste UNC, incluindo o meu Serviço.
Eu só precisava ter certeza de que as credenciais do cmdkey foram adicionadas usando o PsExec como usuário do SYSTEM.
Editado 09/05/2016 - Jon Hoare
O uso de cmdkey para persistir as credenciais ainda não me ajudou, já que meu usuário LocalSystem ainda não conseguiu usar essas credenciais, mesmo que eu as tenha adicionado no contexto do usuário LocalSystem.
O que eu fiz foi realmente criar uma conta LocalUser "Shadow" na minha máquina local. Este usuário tem o nome de usuário da minha conta StorageAccount e eu defini a senha para ser a chave de acesso principal para minha conta Storage.
Meu Windows Service é configurado para ser executado como esse Usuário local e, agora, quando tenta se conectar ao UNC e passa pelas credenciais de sua conta, eles correspondem ao que o Azure exige e a autenticação é concedida.
Espero que isso ajude alguém que está preso como eu fui.