Ok, this is getting really weird… I literally checked everything again in the last 2 hours and I was able to send the CSR successfully a few times - but randomly!
Example:
I started a loop out of desperation. The loop:
while true; do sleep 5; icinga2 node setup --cn ldue-clickhouse-grafana-ds-01 --endpoint do-ffm-icinga-01,x.x.x.165,5665 --zone ldue-clickhouse-grafana-ds-01 --parent_zone do-ffm-icinga-master --parent_host x.x.x.165 --trustedcert /var/lib/icinga2/certs/do-ffm-icinga-01.crt --disable-confd --accept-commands --accept-config ; done
So I basically run the node setup every 5 seconds. The 27th execution of the node setup was successful. The 26 before that and the 9 after that failed again.
The error messages, so that you don’t have to read the whole thread again:
# client
information/cli: Requesting certificate without a ticket.
information/cli: Verifying parent host connection information: host '104.248.241.165', port '5665'.
information/cli: Using the following CN (defaults to FQDN): 'ldue-clickhouse-grafana-ds-01'.
information/cli: Backup file '/var/lib/icinga2/certs//ldue-clickhouse-grafana-ds-01.key.orig' already exists. Skipping backup.
information/cli: Backup file '/var/lib/icinga2/certs//ldue-clickhouse-grafana-ds-01.crt.orig' already exists. Skipping backup.
information/base: Writing private key to '/var/lib/icinga2/certs//ldue-clickhouse-grafana-ds-01.key'.
information/base: Writing X509 certificate to '/var/lib/icinga2/certs//ldue-clickhouse-grafana-ds-01.crt'.
information/cli: Verifying trusted certificate file '/var/lib/icinga2/certs/do-ffm-icinga-01.crt'.
information/cli: Requesting a signed certificate from the parent Icinga node.
critical/cli: Could not fetch valid response. Please check the master log.
critical/cli: Failed to fetch signed certificate from parent Icinga node '104.248.241.165, 5665'. Please try again.
# master
[2019-08-11 21:41:05 +0000] information/ApiListener: New client connection for identity 'ldue-clickhouse-grafana-ds-01' from [142.93.96.49]:57076 (certificate validation failed: code 18: s
elf signed certificate)
[2019-08-11 21:41:15 +0000] warning/ApiListener: No data received on new API connection for identity 'ldue-clickhouse-grafana-ds-01'. Ensure that the remote endpoints are properly configur
ed in a cluster setup.
Context:
(0) Handling new API client connection
The same behavior is reproducible by just running the icinga2 pki request command.
So I start to think that this might be related to https://github.com/Icinga/icinga2/issues/6981? @dnsmichi, @mcktr - what do you think? 
I will try the same procedure in another test env early next week. But any input at this time is highly appreciated.