Ahaha, I forgot I had thought of a different fix before I went to sleep last night, one that some of my solutions (unintentionally) already use :-) (and caikehe's third does, too). In case of a distance-to-target tie between previous closest value and new value (lower in the tree), simply prefer the new value, not the previous. That way, if the target is very large, the result will still be correct. Works for large negative target as well.
So yeah, that's actually quite neat and doesn't require such an ugly additional fix, so I'm now less against large targets :-)