Should block titles be ?
'heading' != 'paragraph heading' (in fact there's no such thing as an HTML paragraph heading). A heading tag is used to denote the heading of a section (a conceptual section, not necessarily a &lt;section /&gt; tag) - it doesn't have to be above, or any where near, a paragraph.

If you're interested in SEO, whatever you do don't convert them from an &lt;h2&gt; to a &lt;div&gt;. A &lt;div&gt; carries no semantic weighting whatsoever, while an &lt;h2&gt; does. If you're not happy with &lt;h2&gt;, obviously choose something else, but for the love of Matt Cutts not a &lt;div&gt; :)

Personally the only tags I'd recommend are &lt;h2&gt; (which is standard for adding a heading to a section in any website, not just a Drupal one) or &lt;h3&gt;, if you're already using &lt;h2&gt;'s to markup more semantically important sections elsewhere in the page.