If you are talking about full fledged employees, payroll related taxes and such is just the tip of the ice berg assuming you offer some other kind of benefits such as health insurance, etc. to employees. And, for the record, I am not aware of any states that don't have some level of requirements to meet. As a minimum, assuming they have income taxes, you always have the issues of having tax numbers and withholding, etc. for the employees, etc. in each state.
With that said, between a decent payroll services provider and your lawyer, this is extremely commonly navigated territory for attorneys to know exactly what is required in each case. Unfortunately, while clearly an unnecessary friction and costs being introduced by your "friendly" state government, it is an inevitable evil that results from getting some level of business success.
Not sure if this is an option, but if you avoid going the employee route, and simply have them working as an independent contractor, all these issues are avoided. All you need to do is file a federal 1099 form for what you pay them each year and all the issues are pushed to them at the personal taxes level. Generally, you probably want to pay them more; to cover their own FICA and Medicare withholding for example (that you would have had to pay Uncle Sam anyway), but it is definitely an option if you are small shop and there is no reason you can't ink a contract that makes the individual feel more comfortable about the arrangement. Again, especially if you pay them a premium some kind.
