You are, obviously, vulnerable on first contact to a site, in that an attacker can prevent you from ever seeing the STS header. The point of STS is that attackers don't generally get to intercept your first contact with a site.
Adam Langley, by the way, is one of Google's Chrome SSL/TLS/HTTPS people.
Similarly: a country savvy enough to have a whole regime for ensuring they have custody of all transactions from first contact on probably isn't a country that offers safe access to browser binaries either, which kind of hurts the utility of baked-in SSL restrictions.
If clearing the browser cache/cookies does not make the browser forget about STS for each domain, then we got another way to maintain http://samy.pl/evercookie/
As an example, a rogue Apple Store employee could insert him self as a MITM between the access point and the internet connection. Anyone testing out a new laptop in the store (or logging in to their bank from a just-activated iphone) would be vulnerable, without the attacker ever having touched any of those devices.