|If it was only going out when you lost power, then a battery change is in order.|
Since you say that it goes out when there is not power issues, then it probably is best to save the battery money and replace the UPS.
A standard 500Watt unit would normally be considered plenty, but it probably will not last 20 minutes during a full power failure. For that, you would probably need a 700Watt to 900Watt unit (that's Watts, not 'VA'). To be sure, sites like APC's probably have a calculator that could tell you even better what would to it.
You have to be a little bit crazy to keep you from going insane.