Heres what i suggest!
As you already mentioned that you cleaned, installed and updated your Nvidia drivers.
Now i would recommend you doing the same again!
Clean the drivers using Guru driver cleaner,
Install the custom drivers,
Now instead of Updating to right now,
nvidia released this patch specifically for Assassins creed 4 Black fag
Though its beta version, but worth a shot