To get SH404SEF working with System Cache plugin, make sure the plugin is LAST in the order settings.
If random å foreign characters appear when cache turned on or when you refresh the page a couple of times.
1) clean the cache
2) try to make sure the random characters aren't in the jos_content table. Using --default-character-set=latin1 should fix this.
3) run the Phoca tool on the database to change the collation to ensure the table collations are set to UFT8
http://www.phoca.cz/documents/38-tools/154-how-to-change-collation-in-database
4) add to line below to the local php.ini file (this is the main fix) :
default_charset = "utf-8"
5) clean cache, hey presto! 2 refreshes and should be fixed.
NOTE: phpinfo() might say the master setting is UTF8, ignore this, forcing the local to UTF8 gets rid of the strange A characters.