To answer my own question:
The CA Certificates / Trusted Public Keys are to be found at:
/opt/zimbra/jdk1.5.0_08/jre/lib/security/cacerts
To list the contents go to that directory and type:
../../../bin/keytool -list -keystore cacerts
(when asked for the password just press enter)
Mine contains 44 certificates, 4 by equifax, which explains why Gmail works just fine while my server does not.
To add a certificate you currently have to use the keytool that comes with the JDK. There are also GUI tools out there to help, like keyman by IBM and
portcle which is GPL'd and quit nice.
I'll file a request for enhancement for this as it is a not-to-uncommon thing to do. Even big CAs like verisign change/add new certificates once in a while.
Link to bug/enhancement:
Bug #16753