I assume you're talking about a computer PSU? They're switch-mode power supplies. Electrolytic capacitors are favourites for causing problems, especially after a few years of use. The advantage of electrolytics is you get high capacitance, small package size. The disadvantage is they're longetivity - they tend to show signs of stress after a few years of use, particularly if subjected to a significant amount of stress.
Usually replacing the defective capacitors solves the problem, assuming you managed to find all the defective ones. If electrolyte has been leaked all over the board it's also advisable to give the area a very good clean and inspect the PCB for damage. If you've still had no joy, you really need to determine what kind of fault the switch-mode PSU has. You mentioned that all of the outputs showed millvolts - this means that none of the secondaries are up and running. The fact that none of them are up and running suggests to me (although it is by no means certain) that your fault is more likely to lie in the primary stage of the power supply. Assuming you've checked the internal fuses, I would tend to check the chopper transistor next. Make sure you fully discaharge the resevoir cap before you do this! If the chopper transistor is short circuit, it's definately worth checking any other surrounding components to see if they are damaged. Sometimes a chopper transistor can fail of it's own accord, but other times it fails because some other fault has caused it.
Other than that, without a schematic of the power supply you're quite limited. You could try checking the start-up section of the power supply, assumung you're easily able to recognise it.
Brian