I agree it was not a programming question actually
Just in case someone else runs accross the same problem with message headers: we didn't manage to somehow changed Lotus Configuration, so we ended up writing a Java class handling all this email stuff, specifying utf-8 for both header and message, and it works now, at least with Lotus and free smtp-servers/web-clients