Кодировка или что-то не так?

Рекомендую настроить smtp почту. Евц это умеет. а не внутренние программы отправки почты из пхп.
Желат по 25 порту.
И ещё попробуйте на хостинге включить iconv а mbstring выключить. Может просто не включены на хостинге средства для перекодировки в утф8