Since you replaced UPS battery since it was new 4 yrs ago, I'd lean towards the low grade PSU then. Have you tried bypassing the UPS all together to see what happens. It could all be the type of PSU and UPS you have. If your PSU has Active PFC, cheaper UPS units don't play nice with them as they're designed for "Pure Sine" units.