Sorry for not getting back earlier. It kinda slipped my mind.
It seems I made a slight mistake in my first suggestion. Try this instead:
PHP Code:
mail($touser[email],$emailsubject,$emailmsg,"From: \"$bbtitle Mailer\" <$webmasteremail>\nContent-Type: text/plain; charset=\"koi8-r\"");
By mistake I had separated the extra headers, instead of putting them in the same parameter, like they should have been.
I have tried this one, outside of vB, and it worked fine. At least it messed up my norwegian letters

(Which was to be expected

)