追記：5年後に同じような症状ではまった。

コーディネータに別サーバーを指定したまま、別サーバが廃棄になったため
MS-DTCが動かなくなった。
コンポーネントサービスのコンピュータ右クリックしてもMS-DTCのメニューが表示されずに困る。
検索したら過去の自分のブログがヒット（ｗ

それでも直らなかったので
以下のリンク先を参考にクリアしたら元に戻った。
http://www.ehow.com/how_7275566_reinstall-ms-dtc.html

わな

コーディネーターの設定は
HKEY_CLASSES_ROOT\CID
に入っているから

一般的な手順によくある
HKEY_LOCAL_MACHINE\Software\Microsoft\MSDTC
を削除しただけじゃ、エラーが解除できなかったんだね。

次からはもう怖くないかも

手順抜粋

(関連サービス停止)
net stop msdtc

msdtc.exe -uninstall

(レジストリキー削除)
HKEY_CLASSES_ROOT\CID
HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\MSDTC
HKEY_LOCAL_MACHINE\SYSTEM\ControlSet001\Services\MSDTC
HKEY_LOCAL_MACHINE\SYSTEM\ControlSet002\Services\MSDTC
HKEY_LOCAL_MACHINE\Software\Microsoft\MSDTC

msdtc.exe -install

(HKEY_LOCAL_MACHINE\Software\Microsoft\MSDTC\XADLLなければ追加）
regsvr32 mtxoci.dll

msdtc.exe -resetlog

net start msdtc

追記

HKEY_LOCAL_MACHINE\Software\Microsoft\MSDTC\XADLL
に以下の追加が必要

文字列値	mtxoci.dll
値	C:\WINDOWS\system32\mtxoci.dll

追記2

AS400とつなぐときはシステムデータソースでないと動かなかった。
ファイルじゃNG