Another gotcha with HSTS + includesubdomains is if you have a naked domain e.g. https://example.com redirecting to a www prefix e.g. https://www.example.com, but the server is configured to send the HSTS header for the naked domain.
It's not always obvious because your gut reaction is "oh my web site is on www.", but that misconfigured naked domain redirect might indeed break "randomservice.example.com".
It's not always obvious because your gut reaction is "oh my web site is on www.", but that misconfigured naked domain redirect might indeed break "randomservice.example.com".