Hello,
This is a very strange problem, I've never encountered something like this. Try disabling the "Ignore multiple sources (Itemid)" option in JoomSEF's configuration, delete all the URLs created and clean the cache so JoomSEF may recreate them.
Or just try not using JoomSEF's cache at all.
Best regards,
ARTIO Support Team