From the IETF draft [ http://tools.ietf.org/html/draft-ietf-websec-strict-transport-sec-06 ]:
10.1 HSTS Policy expiration time considerations
Server implementations and deploying web sites need to consider whether they are setting an expiry time that is a constant value into the future, e.g., by constantly sending the same max-age value to UAs.
For example, a max-age value of 778000 is 90 days:
Note that each receipt of this header by a UA will require the UA to update its notion of when it must delete its knowledge of this Known HSTS Host. The specifics of how this is accomplished is out of the scope of this specification.
Or, whether they are setting an expiry time that is a fixed point in time, e.g., by sending max-age values that represent the remaining time until the expiry time.
A consideration here is whether a deployer wishes to have the signaled HSTS Policy expiry time match that for the web site's domain certificate.
Additionally, server implementers should consider employing a default max-age value of zero in their deployment configuration systems. This will require deployers to wilfully set max-age in order to have UAs enforce the HSTS Policy for their host, and protects them from inadvertently enabling HSTS with some arbitrary non-zero duration.
Therefore, since the browser will update it's stored HSTS max-age on every max-age header recieved [over https], going with the longer time won't really cause any of this bad cache horror story that the gossip talks about. The only issue is if the cert changes. However, site owners should be aware of this and should have the max-age set low (5-8 minutes) right before (a full day or so) the cert change is done due to expiration. However, this is only to deal with an incoming cert expiration (which is mostly avoided by replacing the cert with a new one before the last minute), as can be seen by:
14.6 Bogus Root CA Certificate Phish plus DNS Cache Poisoning Attack
If an attacker can convince users of, say, https://bank.example.com (which is protected by HSTS Policy), to install their own version of a root CA certificate purporting to be bank.example.com's CA, e.g., via a phishing email message with a link to such a certificate. Then, if they can perform an attack on the users' DNS, (e.g., via cache poisoning) and turn on HSTS Policy for their fake bank.example.com site, then they have themselves some new users.
Which shows that cert change in the middle of a broswer's HSTS "session" would not cause problems unless there were problems with the cert (validation warnings or errors). This would render the whole point of your question moot because it assumes that browsers store some piece of information related to the cert sent with the HSTS header response to validate against the HSTS host. As the draft makes no mention of such a concept, I would say that it is an invalid assumption.
However, storing cert information to be used against HSTS hosts can be done with public key pinning. But this would be done at a "factory" level or by the user manually, and as such would also have no way of updating via a HSTS host. [see http://www.imperialviolet.org/2011/05/04/pinning.html for more information]
@Jesper Mortensen: HSTS causes the browser to rewrite all http requests to https before sending them. Therefore you shouldn't have both http and https accesses to a given domain. And anyone implementing HSTS SHOULD (RFC2119) not have a real http facing site (ie redirect on http requests to https via 301 or do something else [see section 6.2]). And mixed context stuff (http to other non-ssl non-hsts domain resources are a problem that is supposed to be dealt with on an implementer basis (by both server and browser)). Also try not to mock its draft status as it is implemented in both Firefox and Google Chrome(ium) [ie. ~55% of all browsers].