url path confusion

You have to add the two permalinks to the SELECT statement like:
"SELECT productcategories.CategoryName, productcategories_2.CategoryName AS parentcategoryname, productcategories.CatPermalink, productcategories_2.CatPermalink AS parentpermalink, products.* FROM productcategories INNER JOIN productcategories AS productcategories_2 ON productcategories_2.CategoryID = productcategories.CategoryParentID LEFT OUTER JOIN products ON products.ProductCategoryID = productcategories.CategoryID WHERE productcategories.Live = 1 AND productcategories.CatPermalink = ? ORDER BY productcategories.CategoryOrder ASC"

Then you can do your links like:

<a class="link-text homepagePanelLink" href="shop/<?php echo($Categories->getColumnVal("parentpermalink")); ?>/<?php echo($Categories->getColumnVal("CatPermalink")); ?>/<?php echo($Categories->getColumnVal("ProductPermalink")); ?>"><?php echo($Categories->getColumnVal("ProductName")); ?></a>

and update your .htaccess to account for the product parameter like:

RewriteRule ^shop/(.*)/(.*)/(.*)$ shop_product_details_s.php?perm=$3 [NC,L,QSA,T=application/x-httpd-php]
RewriteRule ^shop/(.*)/(.*)$ shop_product_results_s.php?perm=$2 [NC,L,QSA,T=application/x-httpd-php]
RewriteRule ^shop/(.*)$ shop_category_results_s.php?perm=$1 [NC,L,QSA,T=application/x-httpd-php]