Hello,
did you try to change the settings of "Use category" and "Use section" switches in JoomSEF configuration?
(if you change it, make sure the old URLs have been purged)
It seems your other problems maybe related to the fact you don't have correct character translations defined. Check the setting "Non-ascii char replacements" in "Advanced configration" section of JoomSEF configuration. You need to define here the translation for all greek characters which are not defined there by default. The format is origChar1|newChar1,origChar2|newChar2,... . (e.g. Σ|S,Δ|D,α|a,...)
If possible, send us access info to your site to
support@artio.net, so we can take closer look on your site and configuration.
Best regards,
Jirka