As Debian has been released my "unstable" box recently upgraded to glibc 2.9.
This caused DNS resolving to mysteriously fail in some applications.
Turns out that only IPv6 enabled applications suffer.
Apparently libc now fires both an IPv4 and IPv6 DNS resolving request in parallel. It looks like some DNS servers don't handle that correctly and answer an error on the IPv6 request before the IPv4 request even has time to resolve further in the internet.
In my case it was my local NSLU2 running Debian lenny causing the trouble, more specific the maradns local DNS server and DNS proxy running on it.
I manually upgraded maradns to the latest version (> 1.3.10) and things are "back" to normal.
Another solution is to disable IPv6 systemwide but I prefer not to do that as I use IPv6 occationally for testing.
I fear that this will cause more trouble for alot of people with routers doing DNS proxying.