This one was very confusing. Lets say you have two stores - one in the US, and one in Japan. You can obviously ship to Japan from the Japanese store (same with the US), but you can also ship to Japan from the US store, and vice versa.
You only have Retail Customer as a group (default), and you've got a list of product tax classes which are shared between the US and Japanese store. So off you go on your merry way setting up US and Japanese tax rates and rules to set the tax - great so far, US customers to the US sare charged correctly, same with the Japanese.
Here is the problem - lets say one of your customers orders from the US store to Japan. They shouldn't be charged tax, but they have been. Why? Magento operates on 3 dimensions with tax:
Note the missing piece of the puzzle - the source! If this were added it would make things much easier, but as it is you're forced to shoehorn some form of identification of source in to one of the other two dimensions, so I beleive the solutions are:
In the situation that caused me this problem, I ended up making per-country tax classes.