The fact that Mail doesn't recognize that certificates are ready to be used and is unable to store them in an efficient way may indicate that your Keychain is damaged...
The first thing to do would be to perform a few maintenance and optimization tasks in order to make sure that no minor disk error or permissions issue could prevent Mac OS X from running normally. In order to do so, follow these steps :
- Boot from the Panther Install CD 1
- Use the Installer <u>menu</u> in order to open the "Disk Utility"
- Click on the "First Aid" tab and repair the hard drive
- Restart your computer
- Use the "Disk Utility" located in your "Utilities" folder to repair the permissions on the Mac OS X partition
Then, try to create a new login Keychain, import your passwords and certificates in it and try again.
Let me know if this helps !