I have Better Store Search installed and paging does not work.

Please open the file app/code/community/TBT/Bss/etc/config.xml

and remove the lines:

<catalog>
<rewrite><product_list_toolbar>TBT_Bss_Block_Catalog_Product_List_Toolbar</product_list_toolbar></rewrite>
</catalog>