bwinzenz Thanks for the response. Regarding where a warning might be placed - I'm not sure where would be best since it's a topic spanning AAD licensing, AAD Connect syncing, and everything around and in between. Because of that (the difficulty of documenting this where the warning will have preventative value), I feel like it's actually something that could merit a feature addition, allowing hybrid Exchange customers to somehow turn off auto-provisioning of mailboxes until the on-premises steps are completed (e.g. either New-RemoteMailbox or Enable-RemoteMailbox, and sync of ExchangeGuid). I can feel this one going the UserVoice path, as much as I fear that is a graveyard for unpopular-but-great ideas.
I will open a case for the failing New-MailboxRestoreRequest and see what can be found out there. In case the error is common or expected under certain conditions, a warning note block could be added to the linked docs page from this blog post. I'll report back once I've gone through support.