OK, I've spent some time looking into this and have learned a few things worth mentioning.
First, there is pretty ample logging of the RPU planning step in the /var/log/xensource.log file. In my particular case it didn't end up being directly helpful, but it's a good resource to be aware of.
Second, it looks like the Xen Orchestra half of the RPU implementation lives here on GitHub. In my case, the error was reported from inside the host.assert_can_evacuate API call that's implemented here inside the xen-api repo.
I don't know OCaml and haven't really grappled with the source code there in detail, but I believe what's happening is that the server is checking that each individual host can be evacuated, but only treating them individually — not taking into account the fact that VMs will be moving from one host to another as the evacuation proceeds in practice.
In my particular case, the logging seems to be saying that this analysis was failing because, as things currently stood, when it would come time to reboot my big-memory machine (mpcxenbackup9), there wouldn't be room to hold its VMs on the other hosts, treating the current VM layout as a given. It has two 64 GB VMs, and only one of the other hosts (the one with >50% memory free) can fit one.
This would be consistent, I think, with other failure modes I've experienced, where the RPU starts and gets partway done, but fails with a not-enough-memory error. In those cases, I think that the assert_can_evacuate checks are passing, but as the VMs reshuffle during the migration, it becomes impossible to migrate a large-memory VM.
I think the solution would be that the planning and execution algorithm needs to be smarter and understand how VMs will move around over the course of the migration; plus I think it has weaknesses in deciding where to send VMs during the process. My system has five 64 GB VMs, which a smart enough packing algorithm should be able to fit at all times no matter which host is offline. But if the algorithm just assigns each VM to the first host that will fit it (in some broad sense), it can get itself wedged later in the process.
(FWIW, my intuition is that, if you only think worry about memory, there will always be a successful plan that migrates VMs a minimal number of times, but that might not be correct. Factoring in other constraints like SRs and networks, you probably need to try a bunch of different solutions with randomization to have higher confidence in finding a fully working migration plan.)