Is there a way to keep redirects (generated by renaming nodes) in sync in Umbraco Cloud across dev, staging and live?

It should just work. As when you do a content transfer it will rename the node and should then generate the redirect.

So - we seem to have found the issue. When we created our cloud site we only used Live. It seems when we created Dev and Staging any redirects created in Live were not synced. If we now do a partial restore from Live to Staging the redirects that were created in Live before Staging existed will not be synced. I will do some futher tests with some new pages.

If the original urls has never existed on the other environments, the redirects shouldn't be needed?

We are using staging as the single source of truth. So if for some reason live became corrupted and we had to restore the site from the staging we would lose all of those redirects. This could create a lot of broken links from historical external links.