First thing to understand is that the WebStore feature is an alpha level feature because it has limited implementation and is not yet a full blown general purpose ecommerce solution. It may not do what you need it to do. The TaxRates as currently implemented works for United States and tax rates are defined at the Country/State level. Tax Rates are applied based on Tax Class, so a product must be marked with the tax Class Taxable. It works only when using direct payment such as with Authorize.NET where payments are processed without the user leaving the site. For PayPal or Google, what I do is configure tax rates in my PayPal and Google Accounts. In my case I only have to charge tax if the billing or shipping address is in North Carolina and it is easy for me to define a tax rate for NC in both.
In reality taxes are a very complex problem because rates and rules vary widely by locality. I do not claim to have a complete solution for it. For example, sales tax in North Carolina varies by County, there is a base state sales tax rate and in each county within the state there are some county tax also added so the sales tax rates vary from county to county and a merchant must collect the correct amount depending on which county(s) the business operates in. So when I configure tax for North Carolina in PayPal, I have to configure the correct rate for Mecklenburg County which is where my business is located. If I had multiple locations it would be even more complicated.
I think you always need to collect at least a billing address to be able to calculate tax at all and it also help enforce credit card security and may be required for you to pass that information to the card processor such as Authorize.NET. When PayPal or Google Checkout are used they collect the billing address and it is returned back to you.
You don't need to configure tax rate for anything with Tax Class not taxable.
Hope it helps,