I'm wondering if I should go out of my way and replace all chars like ÜÖÄ on my site.
I understand that PHP can get these wrong, but is there an actual reason, why I need to put them out as HTML codes, even on pure .html sites?
Basically what is there to gain, and should I care?
Also is it possible that not using or using them has SEO implications?
You should not rewrite working code.
Whether you use characters as such or as character/entity references does not depend on calendar year but on many other considerations, like the ease of typing characters and the difficulty of distinguishing characters when they appear in HTML source. (Can you distinguish a space from a no-break space, or s with comma below from s with cedilla?)
The issue has no SEO implications.
In StackOverflow, this question has been asked many times, see e.g. https://stackoverflow.com/questions/436615/when-should-one-use-html-entities
The short answer is, yes.
Not all browsers will properly interpret those characters. Most will catch your unencoded ampersands and such, but they may not catch less common characters. This has a big impact on user experience, more than SEO (unless it falls in the middle of a keyword you are trying to rank on).
Google uses something very similar in behavior to the Lynx Browser, so if you have the technical ability, you might want to fire that up see how your site looks. You can also see what they scraped from your webpage by looking in Webmaster Tools, but it only shows you the non-interpreted HTML.
The bigger question here, is why wouldn't you encode your characters? The only reason I can think of is that you must be doing it by hand. There are better ways.
First, just type out the text and then drop it in this HTML Encoding Tool, then paste it back into your document.
Second, if you are using PHP, just use the htmlspecialchars() function (documentation). Or, if you are reusing the same ones over and over again, just make them a variable: $U = 'Ü'; which you can then insert using shorthand <?= $U ?>.
Third, just do a big find/replace on all the characters when you finish your document.
There are lots of easy ways to do this and it is still an important thing to do in 2013. So, the long answer is, yes.
