I think the obvious solution is to switch between what I would consider the two “intuitive” answers (1st and 5th on your list) based on the characteristics of the numbers. (a + b) can only fail in cases when both numbers are of the same sign, while (high - low) can only fail in cases where both numbers have different signs.
It would be nicer to have a single equation for it though. I'm going to be thinking about this all day aren't I, damn.
Hmm, just checked and (low + (high - low) / 2) also fails in certain other cases (when both are negative and one is odd I think, but it might be more specific), however it works if you get low and high with the absolute min and max (position relative to zero) rather than just the regular min and max (position relative to -inf).