Method 1, my first choice:
Meticulously clean the board, pads etc of any glue, old solder or flux residue and liberally flux it with a flux pen once clean. Run a couple of fine lines of solder paste towards the middle of the heatsink pad, but away from the edges and not too close together to allow it to spead out under pressure. Clean and flux the mountnig tab on the device. Again, pre-heat the assembly and drop your device in place, put a little pressure on it and hit it with your hot air wand until you feel it seat and settle. Keep the hot air on it for a little longer than you think is too much, to ensure that capillary action pulls the solder all around the pad. Let it cool and then solder up your pins after giving them a rub over with a flux pen. Clean the assembly afterwards of any and all residues left over.
Method 2, not my first choice:
Failing that, and this method assumes that you will not be attempting this again in the future, you could use a tiny amount of Chip Bond (Silver loaded epoxy), again spread around towards the middle of the pad to allow for some expansion under pressure, to bond the device back to the heatsink pad. If you do this, forget about ever removing the device again, it's very unlikely to come back off without wrecking the board in the process. Also, don't get it anywhere other than exactly where you want it, it conducts quite well and will be virtually impossible to remove from unwanted areas. Leave it to set up and cure over night with a little piece of tape holding it in place so that surface tension can't move it, then flux your pins and solder them up. You could also just solder tack two diagonally opposite pins to hold it. Again, clean the board of all residues afterwards.
Choice of solder would be application dependant. If really high working temperatures are involved, like 100 degree C and above, you will need an appropriate specialised solder to do it justice. If it's not getting above an average of 40-50 degree C, then I would just hit it with some good old 60/40 Tin/ Lead and be done with it. You could also go the lead free route, but that will raise your melting point.