I can confirm the problem on your website, but unfortunately I don't know what could cause this.
As we can't reproduce the problem on our test server and we have no other reports of this problem, it seems that it's specific to your web server's configuration. I can only offer you to purchase 1 hour of our paid support service and we would try to debug the problem directly on your server:
www.artio.net/e-shop/support-services/joomla-related-support-1h
You can also use phpMyAdmin to manually export your SEF URLs, they're stored in the (prefix)_sefurls table.