OK, let me explain what I did for future reference.
I managed to make this work with self-generated certificates. Obviously this
is not optimal, but is a solution I could implement right away... Hope this may
be helpful for someone in the future.
I generated a certificate using the "Digital Certificate for VBA Projects" applications
from Office 2010. That would generate a certificate that is valid for 6 years but is
only recognized by the machine where is generated. I created my form template
using this certificate and exported the form. I would then go to the machine where
I need the form to run and open the exported form. I get a security warning message,
and from there i would click on the link to view the certificate, examine the details and
look for the "export certificate" button. Clicking that opens a wizard - on the second
page I selected as the destination for the export "Trusted Root Certification Authorities".
Next time I open the form, the security warning comes up again, and now I can click
on "trust all documents from this publisher". Done - from now on it works with no
security warning and the form runs as full trust. Just repeats this for every machine
where the forms need to run.