Exchange 2003 caracter problems

Hi

I have a problem with a newly deployed exchange 2003 server, the functionallity is ok but when i get mails in the system then sometimes the national caracters æøå is shown as weird caracters *+# or something like this.
What can be wrong??
I think it must be the exchange server that has the problem, since out outlook clients worked fine before on a exchange 5.5.

Hope you can help me with some advice or hints...

Thanks in advance

Gordon
Denmark