Ich habe eine Seite gefunden die mein Problem ziemlich exakt beschreibt und eine für mcht nicht ganz hinnehmbare Lösung bietet:
http://fgiasson.com/blog/index.php/2006/07/19/hack_for_the_encoding_of_url_into_url_pr/
Eine doppelte Nutzung von urlencode() ist keine Option und ich kann nicht in jedem Server die zweite Lösung(recompilen) beibringen...
Ich werde mich mal um die Apacheversion erkundigen.