It DOES require us to collect sales tax for a bunch of different states, though. This would be a big deal if we were an ecommerce company... you'll notice that Amazon is fanatic about avoiding telecommuters; they don't want to accidentally get themselves in a position of effectively raising their prices by 8% on the entire state of Texas just to have one remote employee there.
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.
"...states could still make a case for taxing the former employer."
That makes it sound like if My Company in my state has any interaction with Your Company in your state, both of our states can suddenly make a case that we're both doing business in both states and they'd try to hold us responsible for additional tax.