Aha I get it:
$ nslookup RANDOM_87d6fs87d6f87dsfdasg.fritz.box 8.8.8.8
Server: 8.8.8.8
Address: 8.8.8.8#53
Non-authoritative answer:
Name: RANDOM_87d6fs87d6f87dsfdasg.fritz.box
Address: 127.0.53.53
Everything resolves to that localhost IP address 127.0.53.53
Dont know what for.
EDIT: I guess its Fritz's own mysterious black hole 