Many languages have diacritic signs and there are lots of caches around the world that have diacritic signs in their names. I've just spotted this issue, so please treat it as a good start point for further analysis :)
Let me show you some examples:
"Ćwir, ćwir / Tweet, tweet" http://coord.info/GC4QZ5X -> http://project-gc.com/?wildsearch=%C4%86wir || http://project-gc.com/?wildsearch=%C4%87wir
This one is quite interesting:
"Ósma żona Sinobrodego" http://coord.info/GC5N4N0 -> this works: http://project-gc.com/?wildsearch=%C3%B3sma%20%C5%BCona but those do not work: http://project-gc.com/?wildsearch=%C3%B3sma http://project-gc.com/?wildsearch=%C5%BCona
The other interesting thing is that the search works for Icelandic ð:
Viðey http://coord.info/GC2Q86T -> http://project-gc.com/?wildsearch=vi%C3%B0ey
And now another part, when you go to the following challenge checker http://project-gc.com/Challenges/GC5M8M3/10113 and you take a look to the alphabet config, you will see: "ABCĆDEFGHIJKLŁMNOÓPQRSŚTUVWXYZŹŻ" and it works correctly, it finds caches that start with Polish diacritic signs.
So, I can't see any pattern, but I'm sure that somethings is wrong :) I was hoping to see PGC search working with those characters. Could you please investigate?
PS. Of course if you try to search for "Ćwir ćwir" at the gc.com site, you won't be lucky too http://www.geocaching.com/seek/nearest.aspx?key=%C4%86wir%20%C4%87wir