Thanks Matt. I could possibly play around with Zen cart, but if I can find something off-the-shelf I'd prefer it (and my client is willing to pay for it).

I found something called X-Cart Pro by Qualiteam. Looks promising, though I'm a little unclear about the installation. How do you handle client requests to have software installed on their server? Is it possible? Do you require they purchase a dedicated server?