Then I glued the sticker that came with the cooling paste onto the underside of the heatsink, and smeared some paste onto that. With the accomanying bank-card-like plastic 'applicator', I smoothed it out to cover the whole square. Back went the heatsink plus the fan -- and I also used the vacuum cleaner again to clear up the air intakes of the various fans again (I missed several spots when cleaning it earlier).
So now it's all working again -- I see a slightly better result (2C lower with slightly lower fan speeds), but then again I got me the cheapo version. I ordered a Zalman 7000C-AlCu, which comes with its own tube of thermal paste. Knowing the quality Zalman is known for, this will probably the stuff with silver particles and all that -- so there's no real need to shell out for fancy stuff at this moment.