After I overrode a block template for a primary links, block-edit-link doesn't show anymore...?
Ok, tracked down the reason - every block requires to have a className of block:

&lt;div id="block-menu-primary-links" class="block"&gt;
    &lt;?php echo $block-&gt;content; ?&gt;
&lt;/div&gt;


Once I added this, contextual links regained the functionality. Still not sure where it comes from though, or if it's the only thing sufficient in all cases.