The simplest way to resolve the paradox is that you have a society that becomes more productive over time, and that everyone shares in the increased productivity due to the negotiation process. If you can fish and I can cook, and you discover how to 10x your fishing output while I sit on the beach, you are still going to give me more than whatever amount of fish I got before.
The other thing about Baumol - not his fault - is you often see it quoted as a sort of club to beat people with if you don't like how they make their money. And the fact that it's an economist gives it a respectability that makes people hesitate before asking more.