The HSTS specification tells you not to put those headers in regular HTTP requests anyway.

Also, you're forgetting about browsers that ship with lists of HSTS-enabled sites.