@SilentChris at gmail dot com - I'm seeing the same thing but I'm starting to believe the issue is not PHP but Apache. It looks like Apache's rewrite module is double encoding strings with a '%' sign if they are followed by two or more other characters. So
%25 translates correctly to '%'
%25b translates correctly to '%b'
%25ba translates incorrectly to � which when itself is run through urlencode translates to '%BA'.
Further letters translate correctly.
%25bac produces '�c', etc.
It only appears to happen on the first instance of %25 because further items are translated correctly.