The culprit turned out to be Windows Server 2003 itself. Specifically, Windows Server 2003 Standard SP2. This platform has a problem working well with our application. Our Windows Server 2003 R2 Enterprise SP2 box worked fine hosted on both Virtual Server and (more importantly) Hyper-V.
So, we will be migrating our production application to the new OS, hosting our VM on our Hyper-V box. Which is what we wanted all along.
I have to say that our successful outcome on this project was due to diligent testing. We kept testing different configurations until we had multiple test results, each differing by only one variable. We were then able to clearly define the problem piece of the puzzle.
Thanks to our team for helping with this!