Connection to website cannot be established (randomly)

We manage this website: http://elearning.uem.mz

It is from mozambique (hosted in Portugal), and we have a lot of complaints that the users can't connect to it.

It seems to be a problem with the connection from the user, but we can't pinpoint the exact problem.

What we know is:

It affects randomly (a computer works one day, the next it doesn't);
It seems based on time (a user won't be able to connect for 30 minutes to 2 hours);
Sometimes it gives a Privoxy 500 Error;
Sometimes it gives ERR_NAMES_NOT_RESOLVED;
It affects all browsers.

We created a small .bat script that has to be run as administrator:

ipconfig /flushdns
ipconfig /renew
ipconfig /registerdns

This seems to solve most times, but each issue has to handled individually.

Is there anything we could do to minimize this issue?

Solution

After a lot of time and testing, we found out that this was a problem happening to every other site in the respective country...

It seems to have been some problems/upgrades to the whole infra-structure that was, and still is, messing up most DNS.