I've been working on a customer's Volusion based store, so I'll throw my $0.02 in...
Volusion offers hosted packages with pricing based on number of items in store, or for $10K(US) you can get the source. My answers here, (except for my answer about pricing), are in regards to their shared hosting package(s).
1. Completely customize the look of my site (not be stuck with a template)
Volusion is customizable, although not 100%.. some features of the software are "mandatory" and limit me being able to say you can "completely customize it"... but you can create just about any look you want.
2. Have an SEO friendly URL structure i.e. www.mysite.com/keywords.html
Again, close, but not 100% --- Volusion has built in "SEO friendly" options that allow you to present the (default) .ASP pages as .HTM, but the URL's end up looking like:
(product category names are translated to hyphenated paths and product pages use the database product ID number for a page name).. As you suggest by your question, I too would prefer being able to use /stuff-we-sell/product_xyz.htm
3. Be able to 301 redirect on the page level via .htaccess
Nope, can't use your own .htaccess file.
4. Shopping engine feed compatibility. Can I easily export a feed to the popular shopping search engines i.e. froogle, shopzilla, shopping.com etc.
(I haven't used the feature, but their docs say "...Export feeds to third party shopping marketplaces - including Froogle, Shopping.com, BizRate, Dealtime / Epinions / Shopping.com, Yahoo Shopping, NexTag, PriceGrabber, etc..."
5. Is it compatible with Stone Edge or any other popular order processing software?
It has decent internal order processing, shipping, tracking, etc.. If you are looking specifically for intefration with Stone Edge, some users have posted SQL hacks to export orders from Volusion to SE. (again, I haven't done it, so I can't say if it works or how well).
6. Price - i'd like to keep my set up costs under a few thousand dollars considering that I will handle all of the graphic design.
(Hosted) Volsion starts at $57/mo (100 products), then goes to $77, (250 prod.), $97 (1000 prod), and $197 for unlimited number of products. Next they offer it on a dedicated server (at RackSpace) for $350-$500, and the source code version (if you want to host it yourself, modify it, etc) is $9,995.00
7. Site Search - I'd like to have a good site search
It does have a decent built in search function and ability to build a "Knowlege Base" of info for your customers, link .PDF files for spec sheets, instructions, etc.. to each product
8. Customer reviews would be critical to this site so I would like something that has this feature built in.
The software does have customer review features built in.
Hope this helps.