You can add this to your local.xml
<!-- catalog category default -->
<catalog_category_default translate="label">
<reference name="content">
<block type="cms/block" name="promo_block" before="-">
<action method="setBlockId"><block_id>promo_block</block_id></action>
</block>
</reference>
</catalog_category_default>
<!-- catalog category layered -->
<catalog_category_layered translate="label">
<reference name="content">
<block type="cms/block" name="promo_block" before="-">
<action method="setBlockId"><block_id>promo_block</block_id></action>
</block>
</reference>
</catalog_category_layered>
<!-- catalog search result index -->
<catalogsearch_result_index translate="label">
<reference name="content">
<block type="cms/block" name="promo_block" before="-">
<action method="setBlockId"><block_id>promo_block</block_id></action>
</block>
</reference>
</catalogsearch_result_index>
<!-- catalog search advanced index -->
<catalogsearch_advanced_index translate="label">
<reference name="content">
<block type="cms/block" name="promo_block" before="-">
<action method="setBlockId"><block_id>promo_block</block_id></action>
</block>
</reference>
</catalogsearch_advanced_index>
<!-- catalog search advanced result -->
<catalogsearch_advanced_result translate="label">
<reference name="content">
<block type="cms/block" name="promo_block" before="-">
<action method="setBlockId"><block_id>promo_block</block_id></action>
</block>
</reference>
</catalogsearch_advanced_result>
This will show static block before everything in the category pages and search pages, and you can change before="-" to before="product_list" to show the category title first.