If this issue is completely carrier dependant, with some carriers needing access to the IMEI to work at all, some needing it to work reliably, but also some not needing access to the IMEI at all, I think it would be really useful if everyone reading this thread (who uses Google messages) would also report if they have had no issues at all, and what carrier they use.
Obviously people are already reporting when they have had issues but it might be useful for people to know if there are any carriers that are friendly to GrapheneOS (without needing to give device identifiers / IMEI) as I bet there are people who would switch simply on that basis.
Personally I just use a data sim and don't use RCS yet, however my friend uses GOS and Google Messages and they are pretty sure they've never had issues and haven't had to give access to IMEI.
They are on o2 (in the UK)
When I have a chance I might grab some other SIMs and test them out with RCS support, each for a month or so, and report back for anyone reading this thread who is in the UK.