Would it just be the state tax rate you have to worry about, or would it also include local taxes?
I'm in the state of Washington, and we have to collect sales tax on sales to Washington customers. The tax has to include local taxes. We've got a table from the state giving the rates for each location in the state.
There are 1.6 million rows in the table. The key is a thing called the "location", which is a state-assigned number. Fortunately, it turns out no zip+4 spans a location boundary, so we can use zip+4 to determine the rate. If the state's locations ever end up not being a superset of zip+4 places, then we'd have to go by the full address.
There is another huge table available from the state that lists every single address in the state and gives what location it is in. Of course, people don't always give their addresses in the canonical form that state uses. E.g., someone on "Martin Luther King Blvd" might enter "MLK Blvd", "ML King Blvd", and so on. Or they might say "st" instead of "blvd".
I'm sure a sufficiently clever and determined programmer could come up with heuristics to deal with that. E.g., if the state doesn't have an MLK street but does have MLK blvd, then it could guess that's what the user meant. If there are both, it might tell by street numbers if the ranges don't overlap, and of course there's a good chance those two roads would not be in the same zip code. So it is probably a tractable problem, but a pain in the ass that I sure don't want to deal with.
Now imagine having to do all this for all 50 states. Ugh.
Looking at the Streamlined Sales Tax Project, it doesn't seem very hard at all. It seems like you don't have to bother with any tables yourself; you just connect to a service provider to calculate the tax for you.