>>/160133/
>  この2つのURLは同じ扱いをされるべきだけど、パーセント側は404してしまう。
>  https://www.nicovideo.jp/cache/log
>  https://www.nicovideo.jp/cache%2Flog

　これは別扱いのはずですね。上はcacheディレクトリのlogディレクトリ（またはファイル）になりますが、下は「cache/log」というディレクトリ（ファイルシステム的に「/」が含められるかは置いておいて）になるはずです。
　確か、パーセントエンコーディングは、URIのデリミタとパス名を区別するために作られたものだったはずなので。

>  パーセントエンコーディングって(pathを"/"で分割するよりも前の)pathを受けた時点でデコードしていいんだっけ…

　区別がつかなくなるので、普通はパス分割が先ですね。