Building something like an affiliate shop? We want something very much like Amazon in that some providers define their products in a (site-)global catalog and customers can buy from this catalog.
Customers and providers have the standard features expected from such a system (history, various reports etc etc).

A little peculiarity is that there are no payments or shippings in this system. We are responsible for gathering the orders from customers and notify the providers. The rest is not up to us. 

Which modules do you think we should use to implement such a system ? (Drupal 6)
You've tagged this with ubercart and you're using Drupal 6 so this should be fine - http://drupal.org/project/ubercart_marketplace

If you're not processing payments directly and have some 3rd party integration you're probably best off implementing a custom payment gateway and method using the hooks provided by ubercart than trying to track down a contrib module.