Do you need to pay corporate income taxes in these states as well?
It is possible avoid state income taxes and collecting sales taxes by hiring these employees as independent contractors (if you were willing to give them whatever autonomy was sufficient)?
Do you know if there similar tax consequences to hiring employees who are residing overseas?
(Of course the real answer to all of these is consult an attorney.)
"Doing business" (as far as our accountant is concerned) is having billable clients in those states--generating revenue. We've had employees in 3 states (MI, IL and FL) and the only concern is making sure you are meeting that states payroll tax and withholding policies.
On a related note: Some states have different workers comp laws. We we're not required to carry workers comp in Illinois, but did need it in Michigan (and we also had to insure our Illinois employee, because she was now working for a company that was based in Michigan).
It's a confusing mess sometimes--seek help from accounts and lawyers and don't be afraid to call the state and just ask.
Civil servants are often very smart, and sometimes very bored. Also, unless they are in a position where they regularly face the public, talking to "civilians" can scare them a little - they don't want to be accused of stuffing up. (As long as you are talking off the record, not getting written advice - they hate paper-trails. Written advice is to "double check" that it's all OK).
They can really go out of their way to give free advice.