Hope you hard-working Fellows out there won't blame me for that too hard, but in deed, now as i'm thinking about it, i believe that this Feature is Bullshit.
Using Pretty Permalinks inside the wp_list_cats Function does a nice Job, but the Permalinks-Pathes generated inside the Loop are looking different.
Using the_permalink() and Pretty Permalinks at the same time in a Blog won't be a good Deal for Search Engines - especially for the big G -, because this pretends two different URL's for one and the same Content ;-)...
At the Moment, I have to think about starting a dammed big hack throughout all WP-Classes- and- Functions that are affected with permalinks. I really like WP, but I also know, that creating a new blog-system would be almost the same work.
If there is anybody out there, that has an Idea how to fix this, please let me know, in general.