I need to build an e-commerce store for a very large company - so I am looking for the best, most upgradable product.

I have worked with miva before. Its only downside is that I am not aware of any preformatted templates for it that look nice - like say OScommerce. Are there better solutions with the look and feel setup?

Is miva the best for a large company?

That really depends on the expectations, needs and aims of the "large" company - you really need to look into these things before making a decision. Miva works ok but I think there are better solutions available for these types of customer, along the lines of Pinnaclecart, Jshop etc - these types of carts will give you a lot of flexibility with design and product/order management.

Perhaps the best approach will be to make a list of the important things that your client needs?