Hello Marmeks.
I have fought with certificates for a while, and I know what a pain it can be.
You say the document is pubished on a site, but is it a sharepoint or a another CM? because if that's the case, and the permissions are set right, you could try to publish them without the certificates.
The main template of the document is at the site, so if a user can open a new document, he has sufficient rights, so a certificate might be overkill. (the user has to have an account, sufficient rights AND a certificate).
If the certificate isn't at the extra > options menu, it might be that it isn't supplied with the document for you, you could try reeling it in manually and then try to install it.
Hopefully this was usefull for you, if you've found another solution we'll be glad to hear it from you how you did it.