I’ve been looking into this again.
It seems that when an email arrives as #456; etc it may be because it has been sent in iso-8859-1 format (the way characters are encdoded) and should have been sent in UTF-8 or a yet more universal format. But if you are sending from webmail accounts there is not much you can do, most wont let you change the way (or be able to let you change the way) an email is encoded.
However if you have a email program such as outlook, outlook express or another one there are things that you could try.
There should be a send option in the mail program (for example under tools>options>send, or something like that) and most mail programs will send an email in what is known as "UUEncode" you want to change that to "MIME". This will make your email program send a header on the email with the character set used, you wont see this, but the receiving email program will read it and process the email accordingly (hopefully by showing it properly). Nothing needs to be changed on the receiving program.
Also try sending the email in plain text only, as Rich Text Format and HTML just add another layer of complication and confusion.
If you can’t find these options, or it is unclear what to do, or you have to use a webmail service, you could try writing an email in notepad and saving it as a text file, then attaching it to the email. Depend on how the mail program handles text attachments, it could be sent correctly.
I found this page
http://ourworld.compuserve.com/homepages/PaulGor/index_en.htm which seems to have quite a bit on info on Cyrillic, but I haven’t gone through it all so there might be something useful there.