Put three red balls into an urn filled with ten quintillion vermillion balls and mix them up.
Have you destroyed the red balls?
It's actually worse than this, because the number of permutations is hugely greater, and the red balls are changed in the process. (Which is to say, we're not talking about particles, even assuming we could uniquely identify particles when they are identical in the quantum mechanical sense; we're talking about states of particles, an even more nebulous and ephemeral property of the system.) But the principle is the same: it's not destroyed, per se, it's just mixed in so thoroughly that you can never get it back.
Another way to put it: suppose we take some entangled particles and dump their partners into a plasma; have the other particle pairs been destroyed in the process? No, they're still there. When we measure the states of the saved particles, we don't get meaningful answers, because the entanglement has been mixed in with all the other particles. In principle, if we could measure all those particles perfectly (neglecting uncertainty for a moment, as if), we could disentangle all the particle states, rewind time and confirm that the original entangled particles did, in fact, correlate.
Tim