If I have structural or tool steel that has been treated to some standard (ASTM, SAE, ISO -- e.g., for hardness) but I don't know the details of the treatment, is there a "safe" temperature below which I can work the steel without affecting its performance characteristics?
In general, you want to stay below the recrystallization temperature. Steel is composed of grains, and different types of steel have different grain sizes. The size of these grains affects the steels behavior once it gets past the yield point. At the recrystallization temperature, new grains will nucleate and grow, which undoes any sort of hardening that the steel may have previously gone through.
However, this temperature will vary depending on the alloying elements in the steel, so if you don't know the grade, it'll be hard to know the recrystallization temperature. Unless you're going to be working it around 900°F (500°C) I don't think that should be an issue.
This chart shows the temperatures at which different heat treatments are done.
The answer to your question depends a lot based on what kind of steel and what kind of heat treatment you're thinking of. For one point of reference, if you were working on a steel structure in the United States, AWS D1.1 would limit the maximum heat in quenched and tempered steels to 1100 deg F. This temperature is compatible with preheating for welds or heat straightening.
There are three key temperature which may affect the properties of steel. As mentioned in the accepted answer the recrystallization temperature is the most significant as it can potentially affect any steel, especially ones which have been cold worked to improve their properties or have a high alloy content eg stainless, chrome-moly steels and some castings.
The second consideration is the tempering temperature. This only applies to steels which have been heat treated, generally cutting tools, dies, springs and certain other very high strength/hardness parts. The tempering range can vary between 180 and 300 C or up to 600C for high speed steels. Heating above the tempering temperature will remember the steel and consequently soften it. this is usually only a concern for finished components although some types of stock are supplied hardened and tempered, typically high alloy tool steels.
The final concern is that very high temperatures, approaching the melting point of the steel may cause the growth of very large crystals of even deep oxidation of the surface. This is a concern for all grades but particularly those containing chromium.
Finally, while many hot rolled steel grades can be hot worked without any loss of mechanical properties some have a narrow working window (red short) and the manufacturers data should be consulted in all cases.