As far as I know, the only way to avoid creating a tax nexus in each country where you have "employees" (or contractors) is to make sure the contractors invoice you. The way this usually works is indeed the contractors have a sole proprietorship or legal entity from which they invoice you.

If you just pay them without an invoice but as payroll then congratulations you're now on the hook for all taxes and social security payments in the country your now-employee works in, no matter what's in the contract. In fact you might have committed a crime against local labour law by putting in the contract that you're explicitly not liable for social security payments, benefits or business-side taxes. By not registering a mailbox firm in that country you're probably also committing some crime because this means you couldn't meet any of the local labour law obligations.

This may work while everything is peachy while you pay them a higher amount which they can use to pay their social security themselves, but if your now-employee ever gets a grudge against you, they can easily file a lawsuit against you, and it'll be hard for you to defend. Your now-ex-employee will keep the inflated salary, having not paid the security benefits, and you'll be on the hook for back-paying all tax and social security payments with interest plus a fine.

Especially as a startup you don't want to deal with all these administrative overheads. Just request that each person sets up a business from which they can invoice you, and that they get an accountant to help them with whatever obligations that comes with. You can suggest to pay for the accountant. It's not actually that big of a deal and will allow each person to meet the local obligations, which they (or the local accountant) will know better than you. Note that they themselves then become liable for taxes and social security payments, as someone always is.