Tested & confirmed:
Version 1.5
1.5 gives all duplicate urls, even for absolute single content.
Joomla 1.0.12 (FreeBSD, PHP4). Bummer, Google will not be happy :-)
I suspected linked titles were the problem so I removed them all, experimented with unique ItemIDs, etc., etc. Clearing tables in between of course. Still ALL urls remain duplicate.
ItemID ignore setting is not an option for me, as I use Extended Menu and that is broken if this is set to yes.
Version 1.3.3 reinstalled
Deinstalled 1.5, reinstalled 1.3.3 and hey presto, everything is fine again, WITHOUT ANY duplicate url.
Only changing factor: JoomSEF version.
Yes, there are many issues with Joomla's ItemIDs, but they are not the cause here, the site is exactly the same in both cases.
Hope you find the reason in the JoomSEF code and solve this soon, because JoomSEF is indeed a great component, and it would be a shame if people turn away from it because of this big issue.