Outside the US is a bit easier. How would you hire an out of state employee IN the US who moves to a different state ? You will need to register your business in that state then. Deal/remote.com don't help with that.
Already had that happen. Employee moved out of NY to FL. Did nothing except categorizing him as a FL resident in our HR system. Did not have to form a new business in FL or register as a foreign entity there. Employee lowered his taxes because he is no longer paying NY taxes. Great for everyone!
You may want to double check this. May be your HR System filed stuff on your company's behalf but you absolutely need to have a setup in the state where your employees work and that includes Florida.