You can use electrolytics rated for a higher voltage than the original, as long as you can make them fit. Higher-voltage components generally have better performance than lower-voltage components of the same capacitance, and will generally last longer.
Electrolytics are not operated at their "rated" temperature. The rated temperature is simply the temperature at which they are supposed to last their rated lifetime, which is often only 3000 hours [Edit: or less; Steve has seen as low as 500 hours, maybe even less]. Every ten degrees Celsius lower than the rated temperature should roughly double the life expectancy.
So if the capacitors run at 55 degrees Celsius, a 105 degree capacitor is rated for 50 degrees more, or five decades, so it should last 2^5 times (32 times) longer than its rated lifespan. A 125 degree component has seven decades of safety margin so it should last 2^7 times (128 times) longer.
Also, capacitors with higher temperature ratings ARE designed to run at higher temperatures, and will generally be of higher quality.
Two other important specifications for electrolytic capacitors that are used in power supplies and other power circuitry are ESR (equivalent series resistance) and ripple current. These are not normally marked on the component but you can find them out if you have the manufacturer's name and the capacitor "series", which is usually a two-letter or three-letter identifier marked on the capacitor.
Download the data sheet for the capacitor range, locate the specific part you have, and check the ESR and ripple current specifications. Your replacement must be rated for at least the same amount of ripple current, otherwise it may overheat and fail, and should be specified for the same or lower ESR. (In some circuits, using a capacitor with MUCH lower ESR can cause instability and malfunctioning.)
Also, electrolytic capacitors are not all created equal. As with rechargeable batteries, there is some creativity involved in specifications from budget manufacturers. You should always buy reputable brands - UCC (United Chemi-Con), NCC (Nichicon), and Panasonic (Japanese) come to mind - if you want the device to operate properly and last a long time.