This problem sometimes happens from the early Joomla 1.5, so it seems it's still not solved in 2.5. According to Joomla forums it is not related to specific SEF component, it sometimes even happens with core Joomla SEF, so it is a bug in core Joomla. Unfortunately it happens very occasionally (probably due to some specific server configuration), so it is very difficult to track down.
So if you want to have the cache enabled, we can try to find the source of this problem, but for the above mentioned reasons, we would need to work directly on your server, and because it seems that it's not directly caused by JoomSEF, it would be a paid support service.
If you agree, please purchase 2 hours of our support time at
www.artio.net/e-shop/support-services/joomla-related-support-1h and contact me at
This e-mail address is being protected from spambots. You need JavaScript enabled to view it
with access credentials to your website administration area and to your server FTP.