Also, they'll need to find a Binder who'll permanently sacrifice some of his magic to sustain the vow (are those routinely available for pay?)

Yes. Presumably the person who bound the Auror Legillimancer did so out of pay rather than love. Additionally, Harry could just go find a dying wizard who wants to make some galleons since he's solved that problem. I'd assume that finding a binder is not an obstacle to people like the Malfoys.