Why doesn't subducted earth crust melt?
...the submerging plate is always drawn as deep (seemingly tens of km) into molten rock...


It's actually hundreds of kilometres, not tens of them. But let me correct a common misconception:

The mantle is solid rock. It is not molten rock.

So subduction leads solid rock into more solid rock.


  the surrounding medium is hot enough to melt rock


The surrounding medium is hot enough to melt rock only under very special circumstances, the two most common being:


If the rock gains water somehow (yes, water under pressure helps rock to melt), or
If even hotter rock from down below rises up and decompresses.



  Why are so many textbooks drawing it submerged and unmelted to such depths?


Because it doesn't melt. The subducting plate goes down faster than it heats up. Therefore, pressure increases faster then temperature. This does not allow melting of the subducting slab.

What does happen? The slab loses water. Remember - this was oceanic crust and it's wet. On moderate heating, the water from hydrous minerals (serpentine etc) is lost to the mantle rocks above it. Because the mantle rocks above the slab are hot, the addition of water causes them to melt. We see this all the time in the form of arc volcanoes. The Pacific "rim of fire" is the most famous example of this process.

I would say that some very limited amount of melting may actually happen, but in terms of volume % of the entire slab it's likely to be negligible. The contribution of this melting to global volcanism is also likely to be negligible.