I need a shopping cart software matching the following criteria:
- Can support thousands of different stores, where each store has a
login to manage their products, and they get an HTML to put on their
page (that adds the product when clicked).
- Supports shipping calculations. Perhaps also taxes, and other issues.
- Has a good API for integration with a proprietary payment system.
- Serious high-quality and secure product, with good support.
- Preferrably I can host it on my own Linux server, but hosted
services are also acceptable. Answer should include recommendations of
both types.


Shopping carts I checked so far (oscommerce etc) provide a full
e-commerce system while I need only the shopping cart, so each store
could convert to the new shopping cart without replacing their whole
site.

The answer I'm looking for will include a few leading products with a
comparison of pros/cons.

Example of use:
1. We install the software on our system.
2. We provide a store a username and login.
3. They login, and add their product names and prices.
4. The store gets 'add to cart' HTMLs to insert in their site.
5. A buyer goes to the store and clicks on 'add to cart' of a product.
6. They see their cart (on our server), and can remove items, checkout
or return to the store to continue shopping.
7. Once they finish adding products, they click checkout.
8. Shipping is calculated and added.
9. The payment API is invoked, and the payment system takes over.

oscommerce script (oscommerce.com)
+ B2B module http://www.oscommerce.com/community/contributions,3613/category,all/search,b2b
+ Administration Access Level Accounts 2.0 module
http://www.oscommerce.com/community/contributions,1359/category,all/search,admin+level

Hi I am new to this though I think I understand what you need, 

http://www.clickcartpro.co.uk/ 

This appears to be a generic cart that will do what you need. 

"ClickCartPro is one of the best; it combines a broad-based backend
with a relatively straightforward Web-based administration system.
Best of all, it scales with your needs, allowing database integration
for advanced inventory and accounts control, and providing seamless
access to all the UK's major online payment processing services"

I work with the payment bit hence thats how I know of them. hope this helps

The Pro version of X-Cart will allow multiple vendors to put their
products in one store that shares a common checkout platform.

www.x-cart.com/mall_solution.html

Not sure if this is exactly what you're looking for, but it does have
some pretty good features.