Unfortunately this did not help (not sure if it maybe helped a little bit). Does the order of the parameters in the JS code matter?
Is it possible that it takes a while because there are still some old cookies in use on the user side? (I have added setCookieDomain only recently).
Also the Piwik installation is on another server, may this cause a problem?
In the Piwik settings, when I added this website (Website management), the URL I have entered is example.tld. I guess when I add all subdomains here, referers are ok, but there are too many I’m using. Do I need to enter *.example.tld or something similar there?