@Danp No, it's not quite that. We don't use HA anywhere. But reading the source code I did notice exactly what's mentioned in that bug: in some HA cases, the xen-api code will throw a NOT_ENOUGH_FREE_MEMORY that is just absolutely misleading.
At the macro scale, I think that you could say that the issue I'm running into is that the RPU migrations aren't planned out across the entire process of the RPU. If you have VMs that take up a significant fraction of some hosts' memory, failure to plan the whole process at once can lead the system to get itself "wedged" where it's unable to evacuate one of the hosts.
More narrowly, you could say that the issue is that during an RPU the host evacuation code gives up more easily than it could. Say that you're trying to evacuate host A with a 64 GB VM, and you have two other hosts, B and C, with 60 GB free. It will give up, even if there are VMs that you could move from B to C (or vice versa) that would open up one of them to having 64 GB free. If the evacuation during the RPU was more resilient, then the macro-scale issue would be less of a problem. (Although with a more resilient evacuation command but no large-scale planning, you might end up with an RPU that succeeds but is wildly inefficient.)