> RFC 3986 states that the percent-encoded byte
> values should be decoded as UTF-8.

Where precisely do you read such a SHOULD requirement?
Section 2.5 elaborates that the local encoding (of the
resource) is typically used, ignoring cases where URIs
are constructed on the client system (such scenario is
simply ignored in the RFC).

The last paragraph in section 2.5 is the only place that
seems to imply a SHOULD requirement (although it doesn't
use the keyword); this paragraph only talks about new URI
schemes. Unfortunately, for http, the encoding is of
characters is unspecified (this is somewhat solved by the
introduction of IRIs).