According to the datasheet for the Micron memory modues that this card most likely has, the operating temperature range is supposed to be 0C to 105C. So, if it's really hitting 112, that's outside of the manufacturer's specified parameters for the board's components. You'd think Asus's RMA department would have been briefed on this, particularly since hot-running memory (now that the driver reports it) is a common complaint with 30 series cards.
I don't understand RMAing it over this, though, unless Poland has really terrible consumer protection, where the warranty really is void if you remove the heatsink and check the TIMs. Just Amazon some fresh thermal pads, install them carefully, and run an aggressive fan curve, and you should be good. Maybe also do what Legcramp said, and add some extra pads between the memory heat spreader and the actual heatsink. If silence is that important to you, you probably shouldn't have bought a card this thirsty, but you might be a good candidate for water cooling. A water jacket would definitely fix the hot-running memory.
Also, protip: You can avoid damaging the warranty sticker on most grahics cards by heating it gently with a hair dryer and then using fine tweezers to remove it. Put it somewhere safe, and then put it back when you're done, and the RMA department will probably never notice you messed with it. At least, that works with the little round ones you see on the screws. I've seen a few EVGA cards with a bigger one, and those are a lot harder.
110c is where it begins to throttle, 120c is permanent damage.