Hello. A few months I had the exact same problem. Joomla 2.5 and sh404SEF 4.1 - sh404SEF 4.3. Now it is gone. I'm not sure exactly what helped, but that's what I did:
- Completely disable the cache Joomla.
- Disable the cache URL in sh404SEF. Configuration - General - Advanced - Activate URL cache.
- Disable the cache plugin shlib - Db query cache and programming library. Options Enable db query cache, Enable Joomla! db query cache (only J! 2.x).
- Installed StyleWare Content Canonical Plugin.
I note that the download speed of the site or load on the server not changed. I have a small site (about 2210 URL and 600-700 visitors per day).