we have just launched a new e-commerce site for one of our clients using the Magento platform. It can be a bit tricky to set up but once up and running it's extremely versatile and you can customise it to suit your needs. Depending on the level of usability your require, it's also free, which is nice!
It's well worth reading the forum advice about installation as it really benefits from being hosted on a virtual server.
worth noting...you will still need to use a payment gateway to handle transactions but Magento quite happily integrated with the one we used, which was sage pay. The payment gateway you choose really depends on your client and their relationship with their bank,etc. as to what suits best.