Integrity between two inter-dependant tables

I'm trying to write integrity constraints for a database of DNS
domains. There is a table Domains, a table Hosts (machines which can
be nameservers) and a table Nameservers which links them via their
id. Following RFC 1034 4.1, I need to enforce that every Domain must
have at least two nameservers.

In a typical transaction, we have two INSERT (the Hosts), one INSERT
(the Domain), and two INSERT (the links in the Nameservers table).

I cannot put a trigger on Domains since, the trigger seems fired at
the end of the INSERT, not at the end of the transaction and it
therefore always fail since the links between Hosts and Domains have
not been inserted yet.

I cannot put the trigger on Nameservers for a similar reason.

How to use triggers when the integrity constraint implies several
tables?