Cap maximum wall outlet voltage
You could try using a passive line stabilizer. If  the problem is line fluctuations and not constant brief interruptions, these should be able to keep the voltage to your UPS stable. 

The technical name is “ferroresonant transformers”. These are relatively large and have a limited output power (they use passive components to store energy after all). But these should work well for a small computer load, and have no active circuitry to misinterpret what the line is doing. 

￼ ￼

A similar device a “constant voltage transformer” is a transformer with multiple output taps, and active additional electronics to switch among the taps as needed. It is much more efficient and economic but being active might be an issue.