We could probably handle URLs with empty variables, but the ones with wrong values like product_id=145.html are really strange. Try enabling the URL Source Tracing in JoomSEF's Advanced Configuration - that way the source information will be stored with new URLs, so you can check where are they coming from.
Also when you purge the URLs and they're created for the first time so the website is working, you can set the correct shop.html URL as Active - that way even if duplicate URLs the one you selected will always be used.