Использую форматированный документ в эл. письме
Ставлю в настройках Times New Roman - ничего не меняется, все равно ставит MS Shell Dlg. Где поковырять?
И какой вообще лучше поставить, а то некоторым приходит абракадабра

Выделить фрагмент или область, выбрать шрифт.
Чтобы абракадара не приходила, попробуй ставить кодировку письма в UTF-8.

(1) UTF-8 стоит...
все равно какая то херня приходит - может это быть в настройках почтовика на той стороне?

Вполне возможно в настройках почтовика на принимающей стороне.