Isso é fácil. Você precisa de algo para adicionar ao
smtp_recipient_restrictions = (...), check_recipient_access mysql:/etc/postfix/header_based_on_recipient.mysql, (...), permit
O /etc/postfix/header_based_on_recipient.mysql
deve conter todo o necessário para consultar o mysql, conforme descrito aqui . Não posso fornecer um modelo, pois depende do que você está tentando consultar.
O resultado da consulta deve estar em branco para adicionar nenhum cabeçalho. Ou o resultado da consulta deve ser
PREPEND X-fancy-new-header: Found you in the database
Se você precisar de mais de um cabeçalho, isso não é aplicável. Nesse caso, você deve considerar o uso da interface MILTER com um milter self-made. Fazer essas coisas estendidas não é tarefa do Postfix e é delegado a programas externos, pois o Postfix é um programa de e-mail e não um reescritor de mensagens.
Sinto muito - como um amante do Postfix - recomendar o Exim para manipulação estendida de mensagens, pois essas coisas são incorporadas ao Exim.