Hi Holger!
ich hab von linux kein plan aber ich hatte ein ähnliches Problem auf meinem Win2k client. Da habe ich das Problem mit ipconfig -flushdns gelöst. Vielleicht gibt es bei linus ja was ähnliches.
Wie bereits gesagt, es liegt auf alle Fälle am Client und darum erscheint mir das ipconfig -flushdns gar nicht so abwegig. Ich probiers gleich mal.
Grüße,
Sebi