You are right, there should be no thermal paste on the small IC's Clean it off really good with some denatured alcohol and use a coffee filter to rub it dry and clean let it sit and dry for awhile. Clean and dry the base of the heatsink the same way.
When applying the new thermal compound, put a small rice sized amount on the top of the cpu chip, Press the heatsink down into position but don't lock it down yet. Take the heatsink back off and rub the thermal compound into the base of the heatsink with another coffee filter. This will fill any microscopic holes in the heatsink that you cannot see. Leave the compound on the cpu chip alone. Then place a smaller (half rice size dab) of thermal compound back onto the cpu chip. Press the heatsink back into position and lock it down. This is the procedure I use when building a pc. Coffee filters are inexpensive and leave no residue behind.
Hope that helps !