What do I do if we lost the password to our cert.id?

This is not the answer you want to hear. You're pretty much screwed. You might as well start to rebuild a new environment.

What I highly suggest to prevent this situation takes about fifteen minutes the day you create your production environment. Put your cert.id, server.id, and user.id into a single directory. Include a text file that includes the passwords for all of these files. BURN THIS DIRECTORY ONTO A CD! Place the CD into a sleeve with a letter to your company that hosts your tape library. Include instructions that this CD is not to be released to any person without written authorization from the president of your company. If you don't have an outside company host your backup tape library, put these in a corporate vault or safe deposit box with similar instructions. Make sure that everyone in your IT group who does anything with Notes/Domino knows about this CD. You'd be surprised how much anguish this will save you down the road.