It's really not that big a deal. At Stack Exchange I think we have employees in eight different states now, all individuals working from home. It's a lot of paperwork but not disproportional to the amount of paperwork you have to do per-employee anyway. It does cost something to deal with but it's a rounding error compared to the cost of those people's salaries. It is by no means a reason not to hire people who work from home in other states.
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.
We pay proportional taxes on the % of income that comes from other states. For example, if 80% of our revenue comes from Illinois and 20% from Michigan--we only pay taxes on the 20% from Michigan.
"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.
I've found that calling government offices can sometimes be extremely helpful.
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.