Estoy trabajando en Windows y presenté algunos problemas para instalar la librería pycrypto pero finalmente pude.
Hice un ejemplo donde empleé el AES(utilicé tu función frase_LargoCorrecto), cifré en base64 y pude exportar a un archivo con una extensión deseada correctamente.
En el proyecto real haré la parte visual utilizando la herramienta QT. El tratamiento de la cadena antes de ser cifrada y las validaciones corren por mi cuenta.
*No aplique el MD5 porque desconozco como hacer el proceso inverso.
*en el AES que modo me recomiendas para usar (ECB, CBC, CFB, OFB o CTR)?
Por alguna razón no puedo publicar imagenes del ejemplo, no obstante el código del ejemplo es este:

__author__ = 'Arn_dj'
from Crypto.Cipher import AES
from Crypto.Hash import MD5
import base64
#************MD5*************
def CifrarMD5(cadena):
    c = MD5.new()
    c.update(cadena)
    return c.hexdigest()

def DescifrarMD5(cadena):
    return base64.b64decode(cadena)

#****************AES****************
def frase_LargoCorrecto(frase):
    largo = 16 #todo en aes debe ser multiplo de 16
    relleno = '\x00' #relleno de algo inconfundible
    return frase + (largo - len(frase) % largo) * relleno

clave = 'licencia'
key=frase_LargoCorrecto(clave)

def CifrarAES(cadena):
    a=AES.new(key)
    return a.encrypt(frase_LargoCorrecto(cadena))

def DescifrarAES(cadena):
    b=AES.new(key)
    return b.decrypt(cadena)

#*****************base64*****************
def CifrarBase64(cadena):
    return base64.b64encode(cadena)

def DescifrarBase64(cadena):
    return base64.b64decode(cadena)

#**************Formato de cadena******************
def CrearCadena(entidad,equipos):
    return 'Nombre de la Entidad:"'+entidad.upper()+'"'+"/Cantidad de Ordenadores:'"+equipos+"'"

#**************Crear Archivo******************
def CrearArchivo(nombre,contenido):
    doc = open("D:/"+nombre+".ext", "w+")
    doc.write(contenido);
    doc.close()

print '''
    *****Cifrado MD5/Aes/Base 64*****
    *********************************
    '''

entidad = raw_input('Nombre de la Entidad : ')
equipos = raw_input('Cantidad de Ordenadores : ')
cadena= CrearCadena(entidad,equipos)
print 'La cadena a cifrar es : %s'% cadena
cifrada=CifrarBase64(CifrarAES(cadena))
desifrada=DescifrarAES(DescifrarBase64(cifrada))
print 'La cadena cifrada es : %s' % cifrada
print 'La cadena descifrada es : %s' % desifrada

CrearArchivo("licencia",cifrada)
exit()
**********************Programa en ejecución*********************
C:\Python27\python.exe I:/demolic/keygen.py

    *****Cifrado MD5/Aes/Base 64*****
    *********************************
   
Nombre de la Entidad : telpromt
Cantidad de Ordenadores : 15
La cadena a cifrar es : Nombre de la Entidad:"TELPROMT"/Cantidad de Ordenadores:'15'
La cadena cifrada es : yCjYpC+5x4y9+VhaxC3cOggbfWJ9mr2Apc+JtngQnrQD+UOmfbTSLHDmKQDoG1+CCpX6J3X0onv/SF+HwnYa2Q==
La cadena descifrada es : Nombre de la Entidad:"TELPROMT"/Cantidad de Ordenadores:'15'

Me parece bien codificar la cadena justo como el ejemplo que me diste

Nombre de la Entidad:"TELPROMT"/Cantidad de Ordenadores:'15'

Antes de aplicar el cifrado utilizando por ejemplo el AES deseo primeramente aplicar un cifrado personalizado para después volver a cifrar utilizando las técnicas de cifrado conocidas. En cuanto al archivo en donde se guarde la cadena generada podría ser por ejemplo en formato xml. Cuando me preguntas por el contenido te refieres al formato del archivo. Solo requiero guardar la cadena generada en un archivo. En realidad en cuanto al contenido como tal no tengo ninguna preferencia. Podrías darme algunas sugerencias con respecto a esto. Gracias de antemano

la licencia pude ser un archivo .*  , como el kaspersky que es un .key
o tambien la puedo hacer con caracteres que es como me muestras.

gracias por tu explicacion me ha sido de gran ayuda, pero aun tengo dudas de como complementar todo el codigo para tener el resultado final (el generador)

buenas, en la escuela me asignaron un trabajo final.
consiste en crear una licencia a un programa cliente servidor, la tarea es contrloar la cantidad de pc que se conecten a dicho servidor.
Quiero hacer un generador de licencias que introduciendole un nombre y la cantidad de computadoras me devuelva un codigo o un archivo, para que el servidor reconozca el numero de pc que pueda admitir.

cualquier sugarencia que em puedan dar se lo agradeceria, ya que lo tengo que hacer en python y es un lenguaje desconocido para mi.
saludos desde Cuba...