I had the same problem with certificates as you describe.
I had backup of my old computer and when I copied all files from \AppData\Roaming\Opera Mail\Opera Mail\ it fixed it. But Im not able to tell which file or setting does that.