You have to be a little more 'butch' when desoldering multi legged chips. My two favorite methods are a propane blow torch on low (seriously) on the back of the board, move the tip of the flame evenly but quickly across the back of the board from the components while keeping a steady pressure pulling the chip away from the other side. You'll feel it start to get loose and some point, a quick head count to 2 or 3 and a few more quick passses of the torch and the chip should let go pretty smoothly. I would practice this on junk boards though (I did)
Also using an iron to apply a thick block of solder to each leg quickly and then afterwards reheating all the blobs at once to get the whole thing lose for removal. You'll NEVER desolder those multi legs with a low temp settings, cause you have to get the solder on EVERY leg molten at the same time. You take your chances with what dies from over heating. You could use thin pieces of cut silicon (like a cooking mat) and a small block of aluminum on expensive or sensitive chips to guard the main body of the chip from heat. The silicion insulates without burning or transfering heat and the aluminum sucks up the heat the chip would be getting.
The actual best method is a high airflow temperature controlled hot air rework tool, which is like at he torch method but much more controlled. You really want high heat but for a short period of time. Things like the connectors will act like heatsinks, and so will larger IC's so it's high heat for controlled periods of time that's the real trick. If the legs aren't crimped and you're going after surface mount components I've also heard of people using a toaster oven to heat the entire board and just wait till the parts drop off. The important part is once the part is free is getting it out of the heat, too long in the heat can damage it, but basically if you don't melt the package itself it should be okay. Using a propane torch I often 'blow' surface mount parts off boards with the torch flame even on quick passes. I don't test every bit I get, but they're usually cool to the touch when I pick them up right afterwards. Watch out for via's under chips as it'll let the torch heat go right through the board to the chip.