I have had a long lasting problem using NextGen gallery and tried to solve the matter with their support team. You can read the thread for more information, this is a validated problem:
It turned out that using WP Clean Up to delete redundant data was the cause of the problem and I have validated it on my production site and on a test bed I keep for these purposes.
I can confirm with confidence that using "WP Clean Up" plugin and using it to delete what it considers redundant data (Revision, Draft, Auto Draft, Moderated Comments, Spam Comments, Trash Comments, Orphan Postmeta, Orphan Commentmeta, Orphan Relationships, Dashboard Transient Feed) breaks NextGEN Gallery presentation. I ran the same plugin on my test bed site and as soon as I clicked on "Delete All" button, the plugin cleaned up all the debris but the gallery display is broken.
Since I have run this test on my production site with months of troubles, and now on a test site with minimal content, I will consider the relationship between two plugins "hostile". I will post this message with a link to this thread to WP Clean Up support forum as well.
Just as WP Clean Up author should check what may be causing this harm, it may be prudent for NGG team to investigate that as well just in case another similar plugin may cause the same problem and it may be due to an issue in NextGEN plugin. No other plugins are adversely affected by the cleaning process.