I've raised the issue with the team several times and they have confirmed that the ASN is allowed on our side each time. We don't block on an individual IP level. @mfridrikhson was following up with a similar issue as they were seeing blocks on non-Elastic URLs too, and I'm not sure if he got a resolution.
The only other potential issue I can think of is if you have IPv6 enabled despite using an IPv4 host as IPv6 is not strictly supported. Can you check that?
If not feel free to supply a trace and the response from Hertzner that you have received and I can follow up again.