Question

Thanks for writing out the proof in detail, so that answers can easily refer back to it! The math is fairly straightforward, but as a paradox I find this very interesting.

Spoiler alert: Paradoxes are awesome! If you like paradoxes, don't read below unless you've thought about it yourself first, or just don't care :)

EDIT (Dec. 17, after change in question statement): This answer interprets the question with the values { $x,y$ } varying over possible games. Mathematically speaking this is only an integral more general than the case where { $x,y$ } is fixed (which is the special case where the hosts's choice distribution $Q$ is supported uniformly on two fixed integers), but a new level of potentially paradoxical issues arise. The answer below is intended presuming the fixed case is understood, and addresses issues that arise in passing to the variable case. For a discussion of the fixed case, I recommend Darsh's excellent answer.

---

Logical/mathematical remarks:

(0) An easier method than "repeating until non-integral" is to directly fix a probability distribution $P$ on numbers of the form $n+0.5$ and choose one randomly via $P$.

(1) The proof for this strategy is valid provided that you know the host is choosing his number according to SOME fixed, well-defined probability distribution $Q$ on the integers (but you don't have to know what $Q$ is). In this sense, you know that his choice is actually not completely arbitrary... you know he's following some system, even if you don't know which one.

For example

(1.1) Specifically, consider the step "Averaging over all the cases" (after Case 3 in the question). The number $\epsilon$ in Case 3 depends on $x$, $y$, and your distribution $P$. "Average over all the cases" means that you integrate the function $(1+\epsilon)/2$ over the space of all possible pairs $(x,y)$. This requires a probability distribution on the pairs $(x,y)$, which is where $Q$ comes in. Since any $Q$ will give a result greater than $1/2$, it is tempting to think $Q$ is irrelevant to the conclusion. This is a fallacy! I cannot stress enough that treating an unknown as a random variable is a non-vacuous assumption that has real consequences, this scenario itself being an example. Without this assumption, the step "Averaging over all the cases" is meaningless and invalid.

(2) Although the result of your strategy is that you "know something" about the relation between the two numbers, your confidence in this knowledge is arbitrary. That is, you have no estimate, not even a probabilistic one, on how much bigger than $0.5$ your chances of winning are.

---

Resolving the paradox: (isolating what causes the "weird feeling" here)

In short, I'd say mixing "random" and "arbitrary" in the same scenario makes for a patchy idealization of reality.

Here, one unknown, the choice of ordered pair $(x,y)$, is being treated via a probability distribution $Q$, whereas a related unkown, the choice of probability distribution $Q$, is being treated as "arbitrary". This is a weird metaphysical mix of assumptions to make.

Why?

For example, in science and in everyday life, an estimate of "what's likely" can be accompanied, consciously or unconsciously, with an estimate of how accurate the first estimate is, and in principal one could have estimates of those accuracies as well, and so on. This capacity for self reflection is a big part of being sentient (or at least the "illusion of sentience", whatever that means).

In this scenario, such self-reflective estimates are in principal principle impossible (because we don't assume that the host's distribution $Q$ was chosen according to any distribution on distributions), which makes it a very unfamiliar situation.

This is just one reason why mixing "random" and "arbitrary" can make for a weird-seeming model of reality, and I blame this mixture for allowing the scenario to appear paradoxical.