http://support.microsoft.com/kb/244380

http://serverfault.com/questions/50789/long-pause-when-accessing-dfs-namespace

KB244380 says:
“The DFSDnsConfig registry key must be added to each server that will participate in the DFS namespace for all computers to understand fully qualified names.”

We thought this meant that the registry key has to be set on the DFS namespace servers only, not realising that it was also required on the domain controllers. After we set DfsDnsConfig to 1 on our domain controllers (and restarted the “DFS Namespace” service), the problem vanished.