The varying rates aren't a problem, for certain; Amazon deals with those just fine in various localities (Canada has approximately 10 different rates; I don't think that cities are allowed to put additional sales taxes, as that's reserved to the federal government and the provinces/territories). What's problematic for Amazon (IMO) is the wildly varying applicability rules and filing mechanisms.
I think your idea of a unified sales tax database/system is spot on.