Desconosco como es que se haga el envio mediante CGI... pero no creo que sea muy diferente a lo que se hace en PHP, en el cuál no haces más que enviar HTML común y corriente, como si hicieses una página cualquiera, solo habría que enviar las cabeceras correspondientes. Te invito a que planteés esto en el foro de CGI, quiza monoswim te dará alguna respuesta. También si quieres puedes BUSCAR en el foro de PHP cómo es que se envia un correo... de hecho vista las FAQ que ahí hay ejemplos... solo para que veas cómo se hace, quizá y desde ahí encuentes respuesta.
Saludos y suerte!