epileptic055 I'm having the same issue. I've done ALL the steps above, granting all the permissions including Read Device Identifiers, tried uninstalling/deleting appdata for messaging and all the google apps, restarting, redoing the whole process, multiple times.
Messages setting says RCS is Connected, but it still only let's me send SMS to contacts I know have (stock) Pixels with working RCS. Even checking RCS Connection State in the app's Debug menu (enable it by typing *xyzzy*
in the Messages search box) shows it as connected, with the correct ACS url and everything. I'm really at a loss of what else to try...