"Should" and "May" are such horrible words to encounter when implementing an RFC. Sometimes, implementing workarounds for ends that only implements "Must" is harder than just implementing the RFC as if everything was just mandatory. In my opinion, RFCs should strive to limit the optional parts of a specification at a minimum and, maybe, put the remaining in 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.