Another gotcha with HSTS + includesubdomains is if you have a naked domain e.g. https://example.com https://example.com redirecting to a www prefix e.g. https:/

Another gotcha with HSTS + includesubdomains is if you have a naked domain e.g. https://example.com https://example.com redirecting to a www prefix e.g. https://www.example.com 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".