Have you checked all of the simple things? It's always disappointing to make expensive changes then find out something like the unit has been piped for parallel flow rather than counterflow. There isn't a big bubble of non-condensibles trapped on one side, is there? I've seen people spend a lot of time and money only to find out there's a manual valve someplace that wasn't fully opened, or a pump with a 3-phase motor is rotating backwards.
If this were my project, I'd make sure that there are thermometers and pressure gauges installed across the inlet and outlet piping on both sides of the heat exchanger. The manufacturer of the HX should be able to provide accurate flow data for his unit based on the pressure drops across it. Once the flows are known, it's a simple matter to use the thermometer readings to calculate how much heat is being transferred.