Limitless:
Ceon's Advanced shipper mod allows you to set different shipping methods and locations as well. Not sure if it is applicable in this situation though.
Yes, Advanced Shipper will 100% do what's needed here, no problem whatsoever and it's super incredibly flexible for pretty much any unique scenario one vendor or many vendors may have.
It sounds like the payment aspect could be the stumbling block here. I think you will need to use a central payment system which can be a multitude of systems like Paypal, credit card, check/money order, etc., but you or the site admin will have to be in charge of it and disburse funds to the various merchant participants. I don't see any other way around it.
And thinking about it, but I am not using 1.5.x, but with all of the admin permissions can't you create individual admin accounts and restrict them to just the catalog>categories/products menu and exclude everything else? Can you get specific about which categories they can access? If not, you could probably modify the core to allow this or perhaps figure out a way to clone this page and restrict the accessible categories to specific ones.