Okay, one part of the problem seems to have been the router. I exchanged the thing and suddenly my Laptop gets a valid IP adress via DHCP (Windows XP didn't have any problems right from the start, by the way).
However, the DHCP client does not set DNS-server adresses, thus forcing me to use net-setup once again.
Extremely annoying.
