I think the query would be:
SELECT productcategories.*, products.* FROM products LEFT OUTER JOIN productcategories ON products.ProductCategoryID = productcategories.CategoryID WHERE productcategories.Live = 1 AND productcategories.CatPermalink = ? AND products.ProductLive = 1 ORDER BY products.ProductOrder ASC
and the rewrite rules would be:
RewriteRule ^shop/(.*)/(.*)$ shop_product_details_s.php?perm=$2 [NC,L,QSA,T=application/x-httpd-php]
RewriteRule ^shop/(.*)$ shop_product_results_s.php?perm=$1 [NC,L,QSA,T=application/x-httpd-php]