At least one other similar situation you will encounter are census-designated places. These are usually smaller towns that share a common zip code with a larger area, but have their own town names unique from the main town. Typically, they also have different tax rates.
This can be somewhat easy to solve. If the tax data file you purchased contains this data, you will get multiple tax rates back for the same zip code; each rate should have a different city name. In this case, you can provide the user with a drop-down list of town names and let them choose which one they live in, or you can compare the city they entered with the list you have and find the matching one (or provide the list if nothing matches).
As for your main question, if an address is outside of the city limits, the only way you can get this information is probably through an address verification service which could tell you if the address was inside or outside of city limits. Short of this, there isn't much you can do.
The safe bet is going to be to just charge the sales tax; some people living outside taxable areas may be used to this happening on other ecommerce sites that don't differentiate their address, but this could deter many customers as well, especially when they are placing large orders where they could save a significant amount of money on not paying tax.
If you are dealing with regular returning customers, you could add a flag to their shipping address record that states if the address is in the taxable area. If not, don't charge tax. For new customers however, this would require that they communicate this to you, and that you verify it and update the database (not automatic).
One such service that can provide detailed address information is Melissa Data. Using that address lookup example on their site, it will tell you if an address is within city or county limits. I believe they have a service you can pay for to run these address queries.
