Hi AdityaMukund, replying to your Feb 23 remark:
We do support pagination for majority of cmdlets. Can you please help us understand what commands are you trying to run?
Our use case is an org with >70k guest/MailUser accounts which are mainly needed for validating user certificates in S/MIME secured mail between partners. So we're trying to use Get-MailUser, which only returns a max. of 1000 users, regardless of what paging size is set in Connect-ExchangeOnline & complains about invalid paging/paging timeout.
I did send some details to mailto:email address removed for privacy reasons, but so far not even a confirmation that my mail was received... 
Only workaround we have atm (apart from continuing to use RPS) is to call Get-EXORecipient to fetch all mailusers, then for each returned object call Get-MailUser (but this takes forever compared to the deprecated RPS way)
UPDATE: issue has been resolved. Just in case anybody else is getting the weird 'Expired or Invalid pagination request' error when using REST to fetch more than 1000 objects: apparently, you get this issue if you aren't using the .onmicrosoft.com domain for the -Organization parameter (although this does work in most cases). https://learn.microsoft.com/en-us/powershell/module/exchange/connect-exchangeonline?view=exchange-ps#-organization does state that 'you must use the primary .onmicrosoft.com domain of the organization', so be sure to check that.