E-mails with mail() as UTF-8

Hey again! I'm having major trouble using mail() to deliver UTF-8 e-mails. They get sent and delivered successfully, but seem to be... messed up when they arrive (they go through my ISP's relay e-mail server). My headers basically look like this: "From: Test <robot@example.com>\nMIME-Version: 1.0\nContent-Type: text/plain; charset=UTF-8\n". I want to be able to use UTF-8 chars both in the subject and the body. When I check the letters in my e-mail client (Opera's built-in one -- M2), it shows "UTF-16". Also, the headers look different than from the ones I send. Is the relay server altering my letters? What the hell is happening?