Looking at a recertification nightmare

Our PAB and many of our Administrator functions are the responsibility of a group at our head office. On the admin side, I can set up new users and look after upgrading software etc., but have little experience with more complicated administration issues. This past summer we discovered that no one, meaning no one at our head office had a password for our server certificate. Head office created a new server id and we went through a moderately painful few weeks of issuing cross certificates etc. Last week I tried to set up a new user, and first got a "signature on the certificate is invalid", error, then after some wrangling by the administrator, we got a "public key does not match the one certified", error when setting up the client on the user's desktop. Thankfully we were able to give the user access via iNotes, and it is sufficient for this particular user. However we cannot rely on iNotes as a permanent solution. Now head office is saying that the solution is for us to create new server and user certificates and recertify everyone/everything! I have asked them repeatedly what the ramifications of doing this are, but they have had no experience with doing anything like this on an established group.
We have just under 100 users, but we use Notes heavily for documentation and non-conformance handling for ISO standard compliance, (we have just over 20G of info on 60 interrelated databases). Our server is at release 5.08 and all of our users are currently at Pre-Release 1 or 2.

I have four questions:
1) What can I do ahead of time to ensure the recertification process is as seamless as possible for our users?
2)What should I be checking on the numerous non-mail databases?
3) The user cert we had before was created when we first started using Notes in 1997 and had few features, e.g. no password recovery. Is there an optimal certificate format?
4) Now that Notes6 is available I would like to take the opportunity to upgrade the servers and users at the same time as we recertify everyone. Kind of a ripping the bandage off fast theory - short duration pain vs. long drawn out pain and user irritation. Is this too much to do at one time?