I've used a few carts over the years. The biggest deficiency on most is the shipping module. I've got a little experience with ClickCartPro (10+ years ago), ZenCart, and CubeCart. My very first shopping cart was custom coded, and every little change or add on cost big bucks. Things have sure come a long way since then. They all have their issues. CubeCart is decent and modestly easy to setup, but it does appear to be geared towards allowing developers to sell you add-on modules. Some of the modules are quite good, others are... well... LOL. Important modules like The PayPal payment gateway and a few others are free. Just install what you need. Adding a product to multiple categories is pretty much dead easy, and the built in search engine is decent.
So just out of curiosity. What cart did you go with for the rebuilt site.
P.S. I was wondering why we hadn't seen you in a while. Been busy pulling allnighters getting your site going again. I've sure been there.