Für die Skripte, die Mails versenden sollten, habe ich Mail::Sender verwendet.
Aber das war - glaube ich - nie im CGI-Kontext, geschweige denn FastCGI; eher administrative oder überwachende Skripte, die beispielsweise als Cronjob liefen.

Hast Du denn nur den Eindruck für dieses Verhalten, oder hast Du was Greifbareres?

Anstelle eines DB-Systems, das eine Mail-Queue anbietet, wäre vielleicht auch die Installation eines (lokalen) Mail-Relays überlegenswert. Dieses nimmt die Mails vom FastCGI-Skript entgegen, legt sie in seine Queue und liefert sie dann an den nächstgelegenen Mail-Relay aus.