I'd call Support. Marketo makes it clear that the relationship between Marketo Org and SFDC Org is 1-1 forever.
So the reality of changing that ID could be an issue, even if all of your user names are the same. Please check with the Support team.
It is possible to change the Marketo User or adjust permissions, and you would follow the process you outline for that. But a new Org ID could be a big issue.
I talked to support and got assurance that it shouldn't prove a problem even after letting them know of the Org ID change:
"Thank you for your patience. I have received and update from our Tier 3 team regarding this change. Our team has noted that there would not be any issues once Salesforce migrates your Salesforce instance to a different datacenter. "
I get worried when things seem too easy...
We just received notice that we are moving to a new data center soon, and I'm wondering how the move went for you last year. Did you run into any issues, or do you have any advice on what to do, i.e. disable the sync prior to the move.
How did your move go from one datacenter to another for SFDC?
The transition was seamless and we ran into no issues. We didn't do anything special to prepare for it, and nothing happened to caused us any issues.