You are reasoning from the faulty assumption that "surely it's possible to formalize the problem somehow and do something". The problem statement is self-contradictory. We need to resolve the contradiction. It's only possible by making some part of the problem statement false. That's what the prior over Omegas is for. We've been told some bullshit, and need to determine which parts are true. Note how my Omegas of type 1 and 2 banish the paradox: in case 1 "the money is already there anyway" has become a plain simple lie, and in case 2 "Omega has already predicted your choice" becomes a lie when you're inside Omega. I say the real world doesn't have contradictions. Don't ask me to reason approximately from contradictory assumptions.
You gotta decide something, faced with the situation. It doesn't look like you argue that Newcomb's test itself literally can't be set up. So what do you mean by contradictions? The physical system itself can't be false, only its description. Whatever contradictions you perceive in the test, they come from the problems of interpretation; the only relevant part of this whole endeavor is computing the decision.
This post was inspired by taw urging us to mathematize Newcomb's problem and Eliezer telling me to post stuff I like instead of complaining.
To make Newcomb's problem more concrete we need a workable model of Omega. Let me count the ways:
1) Omega reads your decision from the future using a time loop. In this case the contents of the boxes are directly causally determined by your actions via the loop, and it's logical to one-box.
2) Omega simulates your decision algorithm. In this case the decision algorithm has indexical uncertainty on whether it's being run inside Omega or in the real world, and it's logical to one-box thus making Omega give the "real you" the million.
3) Omega "scans your brain and predicts your decision" without simulating you: calculates the FFT of your brainwaves or whatever. In this case you can intend to build an identical scanner, use it on yourself to determine what Omega predicted, and then do what you please. Hilarity ensues.
(NB: if Omega prohibits agents from using mechanical aids for self-introspection, this is in effect a restriction on how rational you're allowed to be. If so, all bets are off - this wasn't the deal.)
(Another NB: this case is distinct from 2 because it requires Omega, and thus your own scanner too, to terminate without simulating everything. A simulator Omega would go into infinite recursion if treated like this.)
4) Same as 3, but the universe only has room for one Omega, e.g. the God Almighty. Then ipso facto it cannot ever be modelled mathematically, and let's talk no more.
I guess this one is settled, folks. Any questions?