Ok, first I followed this tutorial:
But I did not find out the DNS-adresses of my ISP.
I gave up and made an automatic connection on the XBox - and then, there popped up some DNS adresses.
I wrote them down and then made a manual connection with the given DNS adresses.
Destiny ran for a few seconds longer now. ;)
You need to make your NAT open for the XBox360.
With a D-LINK-Router, this is done like that:
1. Login to your router.
2. Go to DMZ (Demilitarized Zone)
3. Enable DMZ
4. Set the IP of the DMZ host to your XBox-IP.
Restart your router and modem.
Since then, it runs properly.
If you cannot get the DNS-adresses, use the ones from google: 22.214.171.124 and 126.96.36.199
Hope that helps.