2009/9/2 -- 追記: とりあえずC#の側で解決しました。

byte[] b = Encoding.Default.GetBytes(s);
string u = Encoding.UTF8.GetString(b);

要するに、TclはUTF-8をデコードして送ってるのに、C#はシステムのデフォルトエンコーディング（Shift_JIS）としてエンコードしてるようなのです。

だからその逆をたどってやればよいわけで、まず文字化けした文字列をShift_JISとしてバイト列に戻します。これをUTF-8エンコードしてやることで、本来の文字列に戻してやることができるという理屈です。ただし、これはもともとUTF-8で送ってくるクライアントにしか対応できません。2行目が決めうちだからです。

2009/9/2 -- 追記: やっぱだめ

うまくできたと思ったのはひらがなだけで、漢字やカタカナは一部が文字化けしてしまいました（例: 選択 -> 選･）。

ここによれば、一度間違って変換されたものは可逆性を失うようです。
http://dobon.net/vb/dotnet/string/getencoding.html

最初から不可逆なんだからC#で直すことはできないってことになる。

あとはTclからそもそもShift_JISで送れるようにするか、base64でASCIIとして送って、デコードするかしかなさそう。

2009/9/2 -- 追記: 成功

やっぱりbase64でやることにした。いちいち変換しないといけなくてめんどいけど、しょうがあるまい。

Tcl側のポイントは、マルチバイト文字を含む場合は一旦バイナリに変換しないといけないこと。encoding converttoを使う。
C#側はShift_JISのASCII部分だけ使うので、情報の損失がなくなった。返すときは任意のエンコーディングでかまわないようだが、Tcl側で対称性を持たせるためにシステムデフォルト（Shift_JIS）で返すようにした。

Tcl側のコード（エンコーディング省略でシステムデフォルト）

proc dec {s} {
 ::base64::encode [encoding convertto $s]; # Tcl -> C#
}

proc enc {s} {
 encoding convertfrom [base64::decode $s]; # C# -> Tcl
}

C#側のコード

namespace Extension
{
    public static class StringMethod
    {
        public static string Dec(this string s, Encoding encoding) // Tcl -> C#
        {
            var b = Convert.FromBase64String(s);
            b = Encoding.Convert(Encoding.Default, encoding, b);
            return encoding.GetString(b);
        }

        public static string Enc(this string s) // C# -> Tcl
        {
            var b = Encoding.Default.GetBytes(s);
            return Convert.ToBase64String(b);
        }
    }
}

Visual Studio 2008 C#ソリューションとTclのソースを固めて置いときます。ご自由に拾ってください。

1. イベントの定義（ボタンクリックとか）
2. クリップボード操作（CSV/TSVプレーンテキスト）
3. その他もろもろ