Have you tried moving him out, then asking her to move in with him in his new dwelling? And out of curiosity, if you did try to move him out, does she pop up as eligible to move out with him?
With further testing, I did move him out and ask her to move in separately, this appears to have fixed things. When I moved him, I was not given the option to move his wife, but when she moved in, they maintained their married relationship.
I don't understand it but whatever, lesson learned!