That wouldn't work too well with complex RFCs like X509, should is used for some backwards compatibility to earlier RFC revisions and many optional elements that would fragment the standard into dozens of extensions.

IMHO implementors must implement a "should", not in the same sense of the binding requirement that "must" presents, but as a boolean possibility; the element may not be present, but it should never be ignored in a way that would break implementations making use of it.