I'm currently in the "RCS connected, but etouffee not provisioned" state. I had Messages uninstalled for several months since it stopped working, but reinstalled it after I saw the update announcement from GrapheneOS. Followed the directions to enable Phone permission in sandboxed Google Play, installed, checked Messages permissions, started it, then immediately got "Connected", but couldn't send or receive RCS messages because "etoufee not provisioned". Decided to wait at least a day for it to provision.
That night, I got another update and rebooted. Lo and behold, etoufee was now provisioned. I sent one RCS message that night and saw that it was received. Went to send a text the next day, and it failed. Resent as SMS, now showing not provisioned. Turned RCS off and on, and it wouldn't connect (stuck in verifying number).
Put phone in airplane mode, force-quit Messages, erased its data, took phone out of airplane mode, started Messages, went through setup and RCS was immediately connected, but still can't send/receive, because the debug info shows "etoufee not provisioned". Been a day, wondering if it will start working again randomly.