The incorrect aliases are in the ezurlalias table in the db. There seem to be some that are correct and some that have the prepended errors.
There are nearly 20,000 url aliases, so it is hard to review them all.
Yesterday, I emptied the url_alias table in the db and ran updateniceulrs.php to repopulate it. That seemed to fix the problem, but as new users register for accounts, or new pages are published the urls become corrupted again.
For instance, the urls now all have a users name in the url in the contentstructuremenu for the content tree, but in the sub-items view of that content, the URLs are all ok except for pages that have been republished today.
I got this problem one day, and it was hard to solve it.
The problem occured when a new user registered, and then every url was redirected to a module with the name of the user object name.
What I did to solve the problem was to find in ezurlalias the record where source_url was * and delete it.
I am not sure if this will solve your troubles, but it did for me.
I assume something is going wrong when a new object is published. It seems that at one time source_url is set to * and if for any reason publication process is stopped all url (*) will be redirected to this object ...
I haven't seen any likely reason for this problem, so if Nicolas' suggestion does not help I think you have to do some serious debugging. First I would add some debug messages in the class kernel/classes/ezurlalias.php, especially at create, store and updateChildAliases. Then publish one node with a very distinctive name and see what is exactly happening.
In the ezcontentobjecttreenode.php is also a function updateURLAlias which might be worth checking as well.
Data corruption was in the ezcontentobject_tree table - the path_identification_string field to be precise. It's not clear how this happened, but I suspect it could be to do with a script timeout while trying to move large numbers of nodes to new locations in the content structure tree. For some reason incorrect data was being appended to the contents of that particular field.
Running a few manual queries on the database resolved the problem.