Attachment:
umlauts.PNG

for which search engine? can you please paste exact search URL (from the Visitor Log if possible), for keywords where it doesn't work?

It happens with:
Widget:
AOL: http://search.aol.com/aol/search?query=h%C3%83%C2%A4nchen+unterkeulen => hnchen unterkeulen
Yahoo: http://search.yahoo.com/search?p=gefl%C3%83%C2%BCgelbratwurst => geflgelbratwurst
Google: http://www.google.com/search?q=kr%C3%83%C2%B6rken => krrken

These are the links if you click on a search tag below the specific search engine.

Visitor log:
Referer in visitor log which looks nice:
http://www.google.de/search?q=+dicke+sch%C3%A4lrippchen&ie=utf-8&oe=utf-8&aq=t&rls=org.mozilla:de:official&client=firefox-a => displays: "dicke schlrippchen"

http://www.google.nl/url?sa=t&source=web&cd=27&ved=0CDUQIDAQOAo&url=http%3A%2F%2Fwebcache.googleusercontent.com%2Fsearch%3Fq%3Dcache%3AdoULOZ8kcP0J%3Awww.beefstore.de%2Fbs%2Fprodukte%2Fprodukte_anzeigen.php%253Fp%253DWurst%2FSpezialit%25C3%25A4ten%2Bk%25C3%25B6nigsspeck%2Bs%25C3%25BCdtiroler%26cd%3D17%26hl%3Dnl%26ct%3Dclnk%26gl%3Dnl&rct=j&q=k%C3%B6nigsspeck%20s%C3%BCdtiroler&ei=QlNFTMjtA8qBOK-fjIcE&usg=AFQjCNHLrhyUsV6wjgIatHrsgJmgB5_m1g => displays: "knigsspeck sdtiroler"

http://www.google.de/search?hl=de&source=hp&q=k%C3%BCmmelstracke&aq=f&aqi=&aql=&oq=&gs_rfai= => displays: "kmmelstracke"

http://www.google.at/search?q=lammsteaks+aus+der+h%C3%BCfte&hl=de&client=firefox-a&rls=org.mozilla:de:official&ei=a6kvTJKgHtGPOJSH3OAB&start=20&sa=N => displays: "lammsteaks aus der hfte"

http://de.search.yahoo.com/search?p=schinken+eisbein+gep%C3%B6kelt&fr=fp-yie8&ei=UTF-8&rd=r1&sugg=1 => displays: schinken eisbein gepkelt

http://www.google.de/search?hl=de&client=firefox-a&hs=zly&rls=org.mozilla%3Ade%3Aofficial&q=lyonerbr%C3%A4t&aq=f&aqi=&aql=&oq=&gs_rfai= => displays: "lyonerbrt"

PHPMyAdmin: shows it the same way.
db-collation: utf8_general_ci

I hope that I could provide the needed info.
The strange thing is that there a umlauts which are displayed correctly (see new attachment).

Attachment:
umlauts2.PNG

Could you have a look into the DB how the umlauts are stored there?
What is your Database encoding?

PHPMyAdmin: shows it the same way. db-collation: utf8_general_ci

e.g.
%22kochschinken+mit+tr%c3%bcffel%22 => http://www.google.ch/search?hl=de&q=%22kochschinken+mit+tr%C3%BCffel%22&btnG=Google-Suche&meta=

%22schweinefilet+in+aspik%22+ => http://www.google.com/search?hl=de&rls=com.microsoft%3Ade-DE&q=%22schweinefilet+in+aspik%22+&lr=

hnchen unterkeulen => http://suche.aolsvc.de/aol/search?s_it=topsearchbox.webhome&query=h%C3%A4nchen+unterkeulen+&rp=

Is the problem limited to the Search Engines widget (expanding search engine to display keywords), or also affecting the Keywords widget?

Replying to vipsoft:

Is the problem limited to the Search Engines widget (expanding search engine to display keywords), or also affecting the Keywords widget?

yes

Like I tell my wife, that's an either-or question...

According to the provided screenshots, I would say that the problem occurs on both widgets..

I looked in my db for a search engine keyword with german umlaut characters and checked it in both the search engine widget and the keywords widget and all characters are displayed correctly.

Beatgarantie: is this happening with new visits or just old visits? did you re-install or regenerate your config.ini.php, with an existing database?

@vipsoft: seems that the problem only exits with older visits. Search tags this month are ok. I often re-installed and regenerated my installation (using Piwik since 0.4.3).

I think that this ticket can be closet.
Do you have a advise how to make old search tags nice? ;)

Sorry. We don't have an SQL update script for this.

The Piwik installer will configure to use "set names utf8" if the MySQL connection charset isn't utf8. We didn't alter the config for existing users because the conversion is non-trivial and would require regenerating all the archives.