Look at this as a SaaS opportunity. Create a clearinghouse to manage all of the "software". Fairly simple API, you give me the State of the person, perhaps ZIP to find County level taxes and out comes a {"state":".08", "cityX":".01"}. Leave it to the client to handle exact cost calculation.
As for the states that don't have sales tax, they can pay the clearing to provide a {"state":"0"} for all requests.