It's not that hard. Amazon runs Target.com... for which it collects sales tax for every state where Target has a physical store. So it's already a solved problem.

Smaller business could easily outsource this determination; even if every address in the country had its own sales tax rate that's still a tiny database by modern standards.

Still, simplification is a good idea, such as your suggestion there be one rate per state for outside retailers. Perhaps having to face the patchwork would motivate online sellers to lobby for that improvement. Right now they're still shooting for "0%" and I think they have to lose that battle before the necessary simplification can occur.