Hi,
the server is running at the unversity. I've asked the admins and there ist no rate-limiting at all. I've sent queries for 250 hostnames from my home ip (thus, an external non-university source) within 30 seconds and they all got answered. And also queried all our ~ 50 cnames within 10 seconds and got correct replies. So it's no rate-limiting problem...
Also please note that it also happened for the one server that had only a cname, i.e. the real hostname was not contained in the domains. Thus it failed with the one single request for the cname. While the other hosts where I first started fetching the cert only for the real hostname and no cnames all worked fine.
So it seems to be related to cnames somehow. Can I help debugging this further in any way?