Hello,
well, this really starts to sound strange. :-)
Can you give some examples of the links that do not work? Both SEO and original URL, please.
e.g. what is the original URL for:
localhost/de/downloads
(you will find these in the JoomSEF URL viewer/editor)
You might also try purging the URLs (guess it is devel-site so it should not matter) and re-downloading and reinstalling JoomSEF.
Also you wrote this happended after upgrade to 2.0.2, so please test with some older version (2.0.0 or 1.5.1) and let us know using what version it works/does not work.
Best regards,
michal