There are three things that you need to relate in order for an appropriate response to be posted. Do the parts in question wear out, chip out, or permanently deform? If they wear out then you will need a material with greater wear resistance than you are currently using. If the parts chip out, then toughness is the main issue and you need a material with higher toughness. If the parts permanently deform, then they are not hard enough. You stated that you believe the parts are tempering back due to the thermal cycling that they are exposed to during use. If this is the source of your problem, then a material such as a hot work die steel, as suggested by unclesyd, would be an appropriate substitute. H13 may be a good choice because it can tolerate exposures as high as 1000 F for extended periods of time without a significant reduction in hardness. Since your temperature extreme is only 800 F, this would probably work well. But keep in mind that toughness and wear resistance also play key roles in determining how well a material will perform in a given application. You need to consider these as well in making an appropriate choice for a substitute material.
Maui