It seems that for some Apache versions the REQUEST_URI does not return the URI, but instead the running script (i.e. index.php). This causes that pretty permalinks do not function on some platforms.
See thread: http://wordpress.org/support/topic/66770
Is a fix planned? Is there a patch, workaround or plugin available?