Otra cosa que puedes hacer es mediante un .htacces cambiar la forma en que se muestran los productos en la url.
Ejemplo: En vez de: http://tupagina.com/producto.php?id=1
Muestre: http://tupagina.com/categoria/martillo http://tupagina.com/categoria/pantalon
Mira un ejemplo, yo lo hice en esta página
http://www.ventoacoustic.com/productos/Saturn
No creo que tus usarios sean tan curiosos como para cambiar el nombre de los productos en la url, o se cansarían de ver una 404.