Might be prudent to pull and inspect PLCC chips last, unless you're very experienced doing this.
As for the dips, I usually pry a little at each end with a screw driver. If I work slow, in 5 or 6 passes the chip comes out without a bent pin.
Maybe the problem is with the power supply after all. How many amps is the 5 volt rail rated for?
Do you intend to expand this 500?