> возможно у вашего получателя в Германии не активирована кодировка
> русского шрифта. Могу подсказать для Internet Explorer (если не ошибусь,
> делал давно). EXTRS - Internet Optionen-Allgemein-Sprachen.
> Затем выбрать второй язык - русский. После этого в Outlook-Express
> появляются все русские кодировки.
К сожалению, должен Вас поправить - вышеизложенное совершенно не имеет никакого отношения к возможностям IE (а уж тем более Аутлука) в плане кодировок.
Эта настройка (Tools/Options/Languages) совсем для другого - если там поставить первым русский, то некоторые сайты, имеющие 2 варианта своей 1-й страницы, скажем, английский и русский, отдадут браузеру именно русский.

А советы все правильные были даны выше - вроде и у отправителя и у получателя Web-сервисы используются для e-mail (то есть, с почтой работают в окне браузера), а не программы типа Outlook Express или Thebat!.
А для Web-сервисов (например, Yahoo!Mail или тот же Яндекс) правило простое, описанное выше:
- при отсылке: до того, как начн╦шь писать, надо выбрать в меню браузера нужную кириллическую кодировку -
Cyrillic(KOI8-R) или "Cyrillic(Windows")
- при получении - то же самое сделать, если сразу не читается

Кстати, в Outlook Express делается точно так же -
при отсылке в окне подготовки сообщения выбрать нужное, например,
Format/Encoding/Cyrillic(KOI8-R)
при получении - View/Encoding/... если сразу не читается
Подробнее про настройки Outlook Express на русский (чтобы список заголовков читался,...):
http://ourworld.compuserve.com/homepages/PaulGor/cyr_oe.htm