Ex hypothesi, Mary knows all the relevant third-person specifiable color facts. Our inability to simulate her well doesn't change that fact.

It does if our inability to simulate her well messes with our intuitions. If, as I conjectured, we tend to translate "omniscient person" with "scholar with lots of book-learning" then our intuitions will reflect that, and will hence be wrong.

Consider the Marianna variant.....But she still lacks the relevant items of knowledge about what other people experience

Is Marianna omniscient about light and neuroscience like Mary? If she is, she'd be able to figure out which color is which fairly easily.

If it's merely a matter of qualia being complicated, then shouldn't all other complicated systems yield relevantly identical Hard Problem intuitions?

It's not just a matter of qualia being complicated, it's a matter of the human brain being bad at communicating certain things, of which qualia are only one thing of many. And this isn't just an issue of processing power and the complexity of something being processed, it's an issue of software problems. There are certain problems we have trouble processing regardless of what level of power we have, because of our mind's internal architecture. Wei Dei puts it well when he says:

...a quale is like a handle to a kernel object in programming. Subconscious brain corresponds to the OS kernel, and conscious brain corresponds to user-space. When you see red, you get a handle to a "redness" object, which you can perform certain queries and operations on, such as "does this make me feel hot or cold", or "how similar is this color to this other color" but you can't directly access the underlying data structure. Nor can the conscious brain cause the redness object to be serialized into a description that can be deserialized in another brain to recreate the object. Nor can Mary instantiate a redness object in her brain by studying neuroscience.

Furthermore, there are in fact other things that humans have a lot of difficulty communicating besides qualia. For instance, it's common knowledge that people with a few days of job experience are much better at doing jobs than people who have spent months reading about the job.

My intuition is that making Mary superhuman doesn't change that experiencing red seems to narrow down the possibilities for her.

I disagree. If Mary was a superhuman she could study what functions of the brain cause us to experience "qualia," and then study the memories these processes generated. She could then generate such memories in her own brain, giving her the knowledge of what qualia feel like without ever experiencing them. She would see red and not be surprised at all.

If qualia were not a physical part of the brain, duplicating the memories of someone who had experienced them would not have this effect. However, I think it very likely that doing so would have this effect.

Can you explain why this intuition persists for me, when (as far as I can tell) it doesn't for any other complex system?

Because, as I said before, our emotions are "black boxes" that humans are very bad at understanding and explaining. Their Kolmogorov complexity is extraordinarily high, but we feel like they are simple because of our familiarity with them.

Maybe, but in that case the challenge is to explain, at least schematically, what superhuman power Mary obtains that lets her solve the Hard Problem.

I think the ability to study and modify her own source code and memory, as well as the source code and memory of others is probably all she'd need, but I could be wrong.