Continuing the saga, I was able to find someone at Oracle who could duplicate the problem we had been having, and it definitely was the MTS proxy file from Oracle. In particular, its the oramts.dll file, part of the Oracle Services for MTS 9.2.0.4 package. I found Oracle had noted it internally as a bug back in December, but it hasn't been updated in the above package. I was pointed to a zipped version of the oramts.dll to download and install. After installing (actually, replacing the old oramts.dll file with the new oramts.dll file), all of my distributed transactions using COMPlus, ES, ODP.NET, and Microsoft's Oracle Provider worked!
Updated: A patch is available on MetaLink as patch#3252645. Download the p3252645_9204_WINNT.zip file which contains oramts.dll and oramts.dbg, marked as version 9.2.0.4.1, fixing the following issue: BRANCH IN TX GIVES: NEW TRANSACTION CANNOT ENLIST IN THE SPECIFIED COORDINATOR. Obtain the patch if you are using Oracle Services for MTS 9.2.0.4 with OraOLEDB, ODP.NET, and/or Microsoft's System.Data.OracleClient .NET provider.
I am assuming the fix was something similar to what Florin mentioned to us (listed in Sam's post).
