This:
RewriteRule !/index.php?route=(A-Z)/(A-Z)&(*)$ /$2/$3
Isn't what you want. You're going to need 2 types of rules, ones that externally redirect the browser to the URL that you want to see, then ones that internally rewrite to the URL that your system can understand (the "dirty" ones). So something like:
RewriteEngine On
RewriteBase /store/
RewriteCond %{THE_REQUEST} \ /+store/index\.php\?route=checkout/cart
RewriteRule ^ /store/cart? [L,R]
RewriteCond %{THE_REQUEST} \ /+store/index\.php\?route=common/home
RewriteRule ^ /store/home? [L,R]
RewriteCond %{THE_REQUEST} \ /+store/index\.php\?route=product/product&product_id=([^&\ ]+)
RewriteRule ^ /store/product/%1? [L,R]
RewriteRule ^cart$ index.php?route=checkout/cart [L,QSA]
RewriteRule ^home$ index.php?route=common/home [L,QSA]
RewriteRule ^product/(.+)$ index.php?route=product/product&product_id=$1 [L,QSA]
You can't make it "wildcard" like matching because you're changing something like "X/Y" to just "Y", which means when you internally rewrite it back, the "X" part is lost forever.