Why are electrically insulating heatsinks so rare? Is it just cost?
One thing that other answers don't seem to have covered is that you only need a very thin layer of electrical insulator (at modest voltages) while the heat spreader part of a heat sink works best if it's thick.  So it's more efficient to use a thin electrically-insulating barrier followed by a thick, cheap, and easily-made metal heatsink than it would be to use a single piece of a material that's thermally conductive and electrically insulating.  The few materials that do exist (such as diamond) can't be extruded or otherwise easily formed into a heatsink shape.  Some can be sintered but sintering can't generally reach the thermal conductivity of bulk material.  The engineering effect of all this materials science is that we end up doing what we've always done.

Another factor is stock policies: by stocking bulky robust heatsinks and a smaller number (as they're not always required) of small delicate insulating pads your stock occupies less storage space and capital than if you stocked two types of bulky heatsink. Cost and performance are both better without the insulator when it's not required.