I've either used or tested a little bit of everything Shelley. In all honesty, most of them are pretty similar no matter how much they cost.
Xcart has a bit of a unique approach by creating the static pages from the database, however the last time I looked at that one it was still in its infancy.
Last time I looked at Miva it was a bit on the pricey side, but that may have changed. Otherwise, they seem to have a pretty good handle on how to make it search engine friendly, based upon the reviews I've read. Haven't tested it myself lately.
Personally, I've never had the problem of
not being able to get a shopping cart site indexed, but then again I have a few more resources at my disposal since I also run the servers.

Adding a mod_rewrite if necessary is easy for me. Most people don't have that luxury. I also actually like tinkering with code, so it's no big deal when the cart needs a little tweaking. Most would rather cut off their right arm than have to dig into the guts of a shopping cart they just paid good money for.
As to which cart I would use for a new site today... Grumpus told us he developing one a couple of months ago. That's one you can be sure will be 100% SEO friendly out of the box. No idea if he's even gotten it into Alpha or Beta testing yet though. But now that I'm thinking about it I might have to take a trip over to the Cre8 forums to see if anything is posted there about it.
I actually have two new sites in the drawing board stage right now that will both be shopping carts. I'm going to use OSCommerce with both of those and apply a few mods to see how it does these days. It'll be a few months, but as soon as I have some data I'll certainly post it. If I can sort it all out I might even pre-package my tweaks for future use, who knows.
If I were
building shopping cart software these days I'd probably take an Xcart type of approach. Make something that writes the actual files from a database. That's more load intensive during the creation stages of the site, but should actually work out to be an overall advantage since the database wouldn't be constantly hit every time someone visits the site.
hmmm...just what a I need. A new project to entice me!