How about grading the validity of the certificate on a continuous scale? P(site loads) = 1 - R*(days since issue) where browsers can choose R as they wish. This gets rid of this discontinuity.