Hi @photocrati and thanks for the answer.
Unfortunately:
1. Yes, I tried deactivating/uninstalling all other plugins. In fact I went as far as making a brand new WordPress based site with no plugins except NextGEN – same issue.
2. Browser cache is cleaned – I tried both Chrome and IE.
3. I tried different themes, including Twenty Fourteen and Fifteen.
As I observe no one else seem to have this problem, I am pretty sure that it is caused by my server settings. I changed hosting company lately. That’s when it went bonkers.
I asked my hostng provider for the following info:
– MySQL up to date (at least 5.6+)?
– PHP up to date (at least 5.6+)?
– The mod_rewrite Apache module activated?
– PHP Safe Mode OFF?
I’ll get back to you as soon as I got this.