Retrieval of Fritz!Box's honour ;)
I can reach the other machines on the network by their hostname. The Fritz!Box DHCP/Name-server does consider the hostnames given to the DHCP-clients. Only debian doesn't configure the DHCP-client out of the box to provide the hostname. The two gentoo machines do it without any problems.
So, I'm sorry! ;)