The utility of the likely scenarios is essential here. If we don't take into account the utility of $5, we have no obvious reason not to pay the mugger.

No, not necessarily. It could be an arbitrarily small cost: the mugger could say just look at me for a nanosecond, and this tiny action of almost no cost could still not be worthwhile.

If AIXI can not find a full observation history O matching program P which generates a future we would describe as (mugger really does have matrix powers and causes massive negative reward) under the constraints that length(P) < length(O), then AIXI's expected utility decision for the mugger futures goes to zero . The length(P) < length(O) is a likelihood bound.

AIXI essentially stops considering theories beyond some upper improbability (much longer than it's observation history).

but a real observation will not be perfectly optimized to rule out half the hypothesis space.

For AIXI, each observation rules out exactly half of the hypothesis space, because it's hypothesis space is the entirety of everything.

there are more programs that have with more structure than "print this string" that don't get falsified, since they actually have enough structure to reproduce our observation (about K(O) bits) and they use the leftover bits to encode various unobservable things that might have high utility

No - this is a contradiction. The programs of K(O) bits are the first valid universes, and by the definition/mapping of the mugger problem to AIXI-logic, those correspond to the mundane worlds where the mugger is [joking,lying,crazy]. If the program is valid and it is K(O) bits, then the leftover bits can't matter - as you said yourself they are unobservable! And any unobservable bits are thus unavailable to the utility function.

Moreover, they are necessarily just repeats, if the program is K(O) bits, then it has appeared far earlier than length(O) in the ensemble, and is some mundane low utility universe.