we still searching the problem. But to be honest we’ve tested it on our server and it’s working always without any problem. What email provider to you use? Gmail? I remember we had a similar problem with a client, her email provider was Telecom, this company was not able to display the characters from the php mailer.
By the way: the contact form use “php mail” function, not the WordPress mail function, so it could not be the problem.