I think you guys are missing a lot of the point of Mandarin.
Mandarin increases in value the more inconsistent deck quality is in that bank. So having a notrash setup is a huge plus for Mandarin. Efficient cursing, even better. The card doesn't work in fast, slim, engine based banks. You just don't buy it then, except for the on-purchase effect which can be worth cursing yourself when you're trying to get your Gold-Gold-Copper hand up to 8.
The first reason Mandarin is good in polluted decks is because, as someone mentioned earlier, it helps you draw certain cards that you want to see together, and polluted decks need more help with that. You can put action and draw engines together, throne rooms and merchant ships together, whatever it is.
Even more important than that though is that Mandarin lets you get dramatic highs and lows in polluted decks. In something like a Witch notrash game, both players will ruin eachother's decks and muck income down to a consistent 4, 5, or 6. Occasionally you'll get a reshuffle with all your curses lumped together and will be able to buy a province with the hand that is free of them, but not often.
Mandarin lets you lump your hands into spikes. If the rest of your hand has 5$ in treasure, you play it as a terminal gold and just hit a victory card or curse. If you hand has a silver or a gold and little else, you can play Mandarin to kick the one good card to next turn where it has a better chance of spiking to 8. Then Mandarin still buys a Silver or better with that crappy hand - and remember in this game silver is going to be good, it's not a curse.
Sometimes you draw highway, mandarin, silver, curse, estate. Your impulse with that hand is to play your highway, but Mandarin requires a paradigm shift in how you play it. Playing highway with that hand requires you to see 2$ in 1 draw, a tough order to fill. The better play is Mandarin onto your highway, play the silver, buy a mandarin. Now the top of your deck is a highway and a silver. You're going to see 4 more cards in that hand, and they'll only need to total 5$. That's 1.25$ per card instead of 2$ per card, a much easier order to fill.
And mandarin is, of course, great against attacks. That much should be obvious. Unless your opponent is capable of playing a discarder attack every single turn, you can use mandarin to send your good cards to your next hand so that you can buy a province if you aren't attacked next turn. It also has a unique interaction with minion, against a consistent minion deck, you can put crap on top of your deck and be pretty much guaranteed to discard it, so Mandarin works a lot more like a terminal 3$ there.
As for openings, I thought about this a lot. Since you guys aren't easily impressed, I'll just list the best of the openings I came up with:
5$, Mandarin
5$, Mandarin
4$ or 5$ Terminal action: Bridge or Jester or Mine
2$- any 2$ card, or a copper.
The idea behind this is to have 3 purchases during the second reshuffle, getting them all in before the reshuffle. The other idea behind this is that your starting deck has no terminals in it, so getting several of them early creates an advantage. I calculated the odds of drawing so many terminals together that you fail to play them during the second reshuffle. Due to Mandarin's "this goes with this" powers, it came out to like 3 or 4%. Your deck will have 14 cards, so unless both your Mandarins get bottomdecked, you'll have exactly 3 buys before your second reshuffle. Most of the time you'll play both Mandarins, making your deck behave similar to a 16 card deck, as close to a multiple of 5 as possible without being rather risky.
The vast majority of the time, you'll play all 3 terminals with this deck, implying that you'll get 8 copper + 3$ +3$ +2$, so 16$ divided over 3 turns, a 5 each turn. More like 15$ since you'll probably bottomdeck a copper. That's assuming there wasn't a good 2, and you couldn't get anything better than a Monument as your terminal action. And you'll never get stuck with an awkward 7$, if you count it out, it's impossible to 7$ (if it's race to the expand, don't do this). You'll also have some ability to manipulate whether you get 3 5's or a 6-5-4 split of the money.
I think that's a pretty neat lead, but admittedly you need a favorable pool.