Been there, done this a few times, hopefully I've covered all the possible issues below.
The URLs only occur as in the example, no URLs need to have the query string.
domain.com/SOME-PRODUCT-URL?sc=99&category=9999999
If that's your current URL, you need to use that query string (sc and category) to pass to your ecommerce software.
If you want the query string dropped, you must build a database of URLs that translate to your current URLs.
The simpler method using the existing URLs would be to make them:
domain.com/SOME-PRODUCT-URL/99/9999999/
which is like Amazon URLs, that internally translated to this for the software:
domain.com/SOME-PRODUCT-URL?sc=99&category=9999999
If you insist of removing all parameters across the board, then simply build a complete sitemap of your existing software and use that sitemap as a mapping file from old path to new path. This could be accomplished with a simple script.
I would do it all in a SQL file and process the path using PHP or whatever your site is written in and route all requests to the index page and re-route from there.
You really don't want to do this in apache as you will need a rewrite condition and rewrite rule for every single product and category.
Do you really want to make 18K RewriteRule for products and 400k for categories in your .htaccess file?
It's really best handled in the script, not .haccess unless you use a RewriteMap database which requires SSH access to install, it can't be done in .htaccess and hardly anyone knows how to use it, I'm one of those few and I don't recommend it whatsoever.
REVERSE THE PATH IN YOUR PRODUCT PAGE? I'll bet your product database algo being used to create the product URL can be reverse engineered and a simple search for that product in the database will get all the information you need in your product page.
Since you're going to redo your URLs, why not just make them all:
http://www.example.com/p/SOME-PRODUCT-URL
Then this becomes much simpler, you just redirect all pages with /P/ to your product page, then you do a database lookup for SOME-PRODUCT-URL and display the proper page.
Likewise, for categories do:
http://www.example.com/d/SOME-CATEGORY-URL
In the interim, you'll want to make these changes, leave the old URLs working, and add a canonical meta to all your product and category pages specifying the new URL format, which needs to work first, and then Google will transition all the previous URLs to the new URLs.
FYI, you do know that google thinks each page with parameters is a different page so if it currently works with parameters it won't rank without parameters as they're not the same page. This will require a 301 redirect and a meta canonical to fix and it will take a lot of time, weeks, maybe months for the volume you have.
Also, if you have random categories per product and you aren't currently using the meta canonical per product then each category/product combination is a unique page and would create complete chaos in Google. Not 18K products, possibly 400K products at a minmum, or a lot more!
If you haven't done canonicals yet, just doing that will improve your ranking as it merges all those random pages together.
This will not be pleasant but it's like a band-aid over a scab, you just gotta rip it off and let nature take it's course.
Hope this helps and I'd recommend seeking PHP and Google SEO help as well since Apache is hardly the issue with your site.