You should contact your state representative (not member of Congress) and state senator (not US Senator) and let them know that you were denied a well-paying job because of the onerous standards your state has for remote work. They might be inclined to change it.
EDIT: OP mentions the state in question is Florida, which has no personal income tax, but does have a state sales tax (disclaimer: I am also a resident of Florida); I believe a recent court decision on the HN front page [+] makes that a moot point (the business will have to collect those sales taxes regardless of nexus), which leads me to believe their decision not to hire OP was a bit short sighted.
[+] https://news.ycombinator.com/item?id=17365366 | https://www.bloomberg.com/news/articles/2018-06-21/states-ca...
(Online Retailers Can Be Forced to Collect Tax, High Court Rules)
I want to be clear, that I don't blame the state in the slightest. I honestly feel that companies should have to pay taxes where they operate regardless of how many employees live there, but what sucks is that a lot of states have difficult tax codes, esoteric and difficult ways of sending taxes in, have varying laws that make it extremely hard to follow the law unless you are a lawyer familiar with that area, and often won't help you if you need it.
I also don't really blame the company. I still feel like I would have been more than worth the extra hassle, but they aren't sure. And if they can avoid having to pay taxes in that state by not hiring me, and that can provide them a material benefit, then I'd probably do the same as them if I were in their position.
Even the easiest tax system in the world won't make up for the fact that they need to record and charge for tax in that state, then send that money back to the state.
Short of not having sales tax, there really isn't a way that they can simplify it. And again, unless you are a lawyer that knows the tax laws in that area, you won't know how good or bad the local tax system is until you go to try and enter it.
It is weird - and I say this as an Australian - that an employer can be on the hook for employee's moving. it would be much easier if this was managed centrally.
You should. Or conversely, you can look at this as having dodged a bullet.
On paper, they were willing to commit to multiple years of a presumptively-six-figure salary to you (seriously: an employment agreement is a big financial deal, even if it's legally "at will" -- there's a lot of money on the table) but pulled out because of some fear of bureaucracy and (maybe) a tax increase? That tells me that the commitment they were thinking of putting on paper wasn't worth, heh, the paper.
That's not a loyal employer, basically. If they're willing to cut corners with the State of Florida they'll do it with their own employees too.
Cutting corners would be hiring an employee as a contractor in order to avoid dealing with the new state’s laws, or simply punting on acquiring any research or consultation, which would actually endanger the OP’s employment status. Perhaps you are used to companies operating this way, but it’s not a sign of a good employer.
The USA is like that on STEROIDS. You can have 3 levels of income tax. that's insane! I can't image the costs of being complaint with that - not least of which is the cost of making an accidental mistake. I doubt many small businesses want to be experts in {INSERT STATE HERE}'s tax regulations and laws. Far easier to avoid the headache if at all possible.
And if you don't think that is the case, imagine instead of states it was countries. How much does a US company want to deal with Haitian laws?
The choice wasn't "hire someone or don't hire someone", it was "hire someone that will complicate taxes and cause more expenses, or hire someone else of similar salary and skill that doesn't cause those issues".
South Dakota's recent win at the Supreme Court[2] related to collecting sales tax from internet sales was due in large part to SD's very pragmatic and fair approach for out-of-state sellers (doesn't require you to know/care about local sales tax fluctuations and only want a base state-wide rate, exempts sellers with less than $100k of sales to the state, etc).
I'm with you in that I don't blame the state for wanting to collect taxes; stuff has to get paid for somehow, and states don't have the same infinite/unbounded pocketbook that the federal government has. But don't disregard what you said immediately after that - the difficulty with compliance is a huge hurdle. If the company could have made compliance a minor additional cost, they could bake that into their decision. Instead, it was an unbounded additional cost with unknown future repercussions and required heavy ongoing administrative work (it's another legal/accounting variable that adds potentially non-trivial overhead to all future legal and accounting work).
The streamlined sales tax stuff demonstrates the same type of collaboration that could be done to simplify remote employee administration, without having the full compliance baggage that comes with the same level of administrative overhead as if you had a full fledged office in the state. Doing so would make it far easier and less onerous to hire remote employees (or allow an on site employee to keep working for you if they move out of state). So it's still worth raising the issue to political figures, as it's very similar (if far smaller in magnitude) to the revenue loss they had by not making it easy to comply with sales tax stuff.
[1] http://www.streamlinedsalestax.org/ [2] http://thehill.com/policy/finance/393441-supreme-court-rules...