Se o seu MTA suporta catch all, por que você não pode encaminhar as respostas com o mesmo recurso e descartar o Gmail completamente?
O envelope from é o endereço que tem que suportar VERP, porque a única maneira de identificar de forma confiável a causa de uma rejeição é através das informações no endereço do envelope from do e-mail original, como Michael explicou anteriormente.
Tenho minhas dúvidas sobre essa afirmação. Usar um endereço do Gmail para respostas é gambiarra, e sempre foi gambiarra; o receptor de e-mail é uma maneira muito mais direta, confiável e com menos gambiarra de lidar com respostas (e rejeições).
Mesmo para esses sites pequenos que usam o Gmail, os realmente minúsculos provavelmente estão ignorando os Termos de Serviço e usando o Gmail para retransmitir a saída também, e a grande maioria dos outros provavelmente não está presa a um MTA que não suporta endereçamento detalhado.