For this specific problem I now found a solution myself using iconv.
$decoded = iconv( 'ISO-8859-1', 'UTF-8', urldecode( $encoded ) );
I think the standard charset being used for urlencode/urldecode in PHP >= 5.4 is now UTF-8, although I didn't find anything in the changelogs for these functions specifically.