First, what was the reason for the heater changes?
Which windows fog up, the windshield or the side windows? If this is happening, it could be because the vent cables aren't properly adjusted, meaning they're not sealing and are letting in air, either hot or cold. If they're cable-operated, you'll hear a noise when you move them as they hit the walls where they're supposed to seal. This applies if your control is manual. If your control is electronic, these are moved by small electronic motors. It's possible they're not completing their full range of motion and are faulty. They would need to be replaced, but you'd have to disassemble the car a bit to access and check them.
Let's assume the vents are moving fully. If it's an older car, it's very likely that the vents have lost their seal, which is why, even if the vents reach their full range, they're not sealing properly. And you're experiencing air leakage through the vents.
Now, regarding the cold air coming from one side and warm air from the other, it could be due to a lack of refrigerant in the A/C. In some cars, when you recharge the refrigerant, the air starts cooling from left to right, and in others from right to left. Unless you have individual heaters. As for the fluid the mechanic recommended, what's the reason? I personally don't recommend those fluids.
I hope this helps. Let me know if you need anything else. Best regards.