If Your RMS had failed prior to Service Pack 1, and you didn't have a backup of your encryption key, You were in trouble. Your only option was to rebuild from scratch.
Now with SP1, we have a new CREATE_NEWKEY command line switch that can make recovering from a situation like this potentially much easier. We also made running the encryption key backup process a mandatory process of setup, just so you'll have a friendly reminder.
Continue reading at our new blog – OpsMgr 2007: What if I lose my RMS encryption key!?