My own encounter with rust monsters was in a 12th-level game, in which the DM sicced two fiendish rust monsters on us in the basement of one of the BBEGs' front operations. We knew what they were, I think the party wizard even made his Knowledge check in-character, but there was no room to manouever. Before we could nail them both, they'd eaten my cleric's enchanted dwarven full plate, and the paladin's holy avenger.
Fortunately, the DM wasn't being totally cruel - this was in one of the largest metropolitan areas in the setting, with major temples to both our characters' deities, so we had some resources to call upon for replacement equipment - which didn't stop it making a major dent in our finances, and more specifically stopped us dead in our exploration of that building (as in "okay, wizard, teleport us the hells out of here before some more come along!").
Just as well we stopped, too - the two rust monsters had come through the same portal that the guy we were tracking left via. When we scryed on the destination, the DM's description was "You see a very large room. The area you're looking at is illuminated out to 30 feet, and you see a large number of rust monsters with glowing red eyes. Further back, beyond the light, more identical sets of eyes can be seen glowing as far back as you can see."
Actually, I don't think we ever did visit there, not even after I bought a set of dragonhide full plate, and the paladin and I both bought gauntlets of rust.