Which provided the following solution:

certutil -setreg ca\setupstatus +512
net stop certsvc
net start certsvc

And now Microsoft issued KB967332 5 months after that post.

INFO  [RES] Network Name <vdmprinters>: Initiating the Network Name operation : 'Verifying computer object associated with network name resource printcluster'
INFO  [RES] Network Name <vdmprinters>: Trying to find computer account printcluster object GUID(b4a849281d4b47d30af3681b8590a20e) on any available domain controller.
INFO  [RES] Network Name <vdmprinters>: Found computer account printcluster on domain controller \dc1.domain.local.

Just a very interesting series of posts by Jorge on how the Active Directory clients determine which domain controller servers their logon request and which domain controller sends the GPO files over.

DC Locator process part 1
DC Locator process part 2
DC Locator process part 3

A small add-on: using start - run - cmd and execute "set" you can easily determine your logon server. Determining which DC sent the GPO's can be determined by running "gpresult /R" (Windows 2008) or "gpresult" (Vista)

The following Technet article is also a nice source of information: How DNS Support for Active Directory Works

[Update:] added NTP as said by Brent in the comments

The following post will explain how to let basic Active Directory related network traffic such as logon requests or replication traffic, be it either sysvol items or AD objects, happen through firewalls. This doesn't mean I'm totally in favour of implementing a firewall between every possible environment. But you might encounter projects where firewalls are used between different sites or just internally between clients and servers.  In that case you might find the following interesting:

The following list is an overview of the AD related services with their required ports:

• NetBIOS name service (137/tcp, 137/udp)


• NetBIOS datagram service (138/udp)


• NetBIOS session service (139/tcp)


• SMB over IP (Microsoft-DS)(445/tcp, 445/udp)


• LDAP (389/tcp)


• LDAP ping (389/udp)


• LDAP over SSL (636/tcp)


• Global catalog LDAP (3268/tcp)


• Global catalog LDAP over SSL (3269/tcp)


• Kerberos (88/tcp, 88/udp)


• DNS (53/tcp, 53/udp)


• WINS resolution (if required) (1512/tcp, 1512/udp)


• WINS replication (if required) (42/tcp, 42/udp)


• RPC endpoint mapper (135/tcp, 135/udp)


• AD replication (TCP 1024 - 65535*)


• FRS replication (TCP 1024 - 65535*)


• Netlogon (TCP 1024 - 65535*)


• NTP (123/udp)

It all seems fine but those last 3 entries are quit funny. If you ask your security guy to implement those, he might aswell just throw his firewall out of the window. Microsoft describes this situation as turning your firewall into swiss cheese (Technet: Active Directory Replication over Firewalls).  A second solution is to set up an IPsec tunnel. Something in between is the option to restrict certain RPC services to a specific port. There are a lot of services which use RPC to determine the port they are listening on. Domain replication, file replicaton, netlogon, remote eventviewer, remote computermanagement are all examples. Whenever such a service is started the "RPC end-point mapper", a service which listens on port 135, decides which port the service will actually listen on (between 1024 and 65535). This behaviour is nicely explained in the following posts over at the (Microsoft Networking Team: RPC Endpoint Mapper in a network trace and RPC to Go v.1)

By choosing those ports ourselves and fixing the services to listen on those port we can actually limit the required ports to be opened to 3 single ports:

• AD replication:

HKEY_LOCAL_MACHINESYSTEM\CurrentControlSet\Services\NTDS\Parameters\
DWORD: "TCP/IP Port"
value: port1

• Sysvol replicaton

HKEY_LOCAL_MACHINESYSTEM\CurrentControlSet\Services\NTFRS\Parameters\
DWORD: "RPC TCP/IP Port Assignment"
value: port2

• Netlogon traffic

HKEY_LOCAL_MACHINESYSTEM\CurrentControlSet\Services\Netlogon\Parameters\
DWORD: "DCTcpipPort"
value: port3

Don't forget: A reboot is required

Note: actually only sysvol and ad replication traffic is required for two domain controllers to talk across a firewall. The netlogon service is only required when you want to handle logon requests or domain joins accross a firewall. This might be the case when you're setting up a new site and at first you don't have that Domain Controller available to handle your requests.

Microsoft KB's which explain the given registry keys:

KB224196 and KB319553