Same issue, Intune Company Portal needs to create the work profile but is unable to do so completely, by that I mean you can see under accounts the work profile settings / remove work profile but Intune cannot conclude the process successfully.
As you I think this is due to GrapheneOS nature since Intune is in fact a glorified keylogger that require admin perms yet I also felt the need to install it in order to avoid using 2 phones or set to workarounds like Sync2 (that use Google services....), the usual debacle between convenience and privacy...
So I'm still deciding what to do...