Browsing through the nagios source code i thing that the "problem" occurs at the url_encode() function (declared at the cgiutils.c file) that is used to encode any special characters in the cgi parameters to the URL format.
As long as i can see it retains the values of ASCII alphanumeric characters and converts any character (byte) with value <= 0x20 (=32 decimal) to a '+'. The rest of the bytes are represented with their hex values.
Obviously the greek unicode (multibyte) characters are considered <= 0x20 and are converted to '+'
Is there a utf_8 compatible version of this routine?