From a newsgroup post: "If you re-provisioned your RMS server, then I suspect the user that sent the email still has a publishing license that was signed by the original instance of RMS. The new instance of RMS will not be able to provide use licenses for content protected by those legacy credentials (unless you import the old key material as a "trusted publishing domain"). This is only possible if you exported/backed up the key material before you re-provisioned.
You should make sure that any clients that received credentials (RACs and CLCs) from the legacy RMS server remove those credentials and get new ones from the current RMS server; otherwise, you will keep having this problem. The RACs are valid for a year, and the CLCs do not expire, so the clients will merrily continue to use them as long as they are there on their systems.
Clients can remove their old credentials by opening an RMS enabled app (like Word 2003), selecting File -> Permission -> Restrict Permission As, selecting their email address and clicking "Remove". The next time they try to use an RMS function, they will automatically go get a new set of credentials from the new server".