I believe that such being cannot exist, and therefore the problem is a logical impossibility, but for different reasons than Martin Gardner.

One thing I can decide to do is flip a coin to decide. In order to predict what I will do, the being has to be able to predict how the coin will land. In fact, I can use something harder to predict than a coin: I can use something truly unpredictable, governed by quantum mechanics: I'll set up a single radioactive atom and observe whether it decays or not in 1 half-life.

In such a circumstance, the being can never be better than 50-50 with me, no matter how smart s/he is, so the paradox goes away.