Yes, all possible. I don't think any are easy in terms of doing it by manipulating settings. You would have to customize the code. Its not a bad idea for a contribution actually. For my store I have no competition practically but I still hardly sell ANY product in my own province. There's really no reason for that other than taxes. I myself, when shopping online, try to stay away from businesses in my own province because I don't want to pay the extra 7% for no reason. Which is why provincial/state taxes suck - but that's an entirely different discussion.

One problem you're going to run into is that your site doesn't know where a customer is from until they log in. So you'll basically have to advertise somewhere that you pay the taxes for local orders. Then you need to modify the code such that a discount is automatically applied for those in the tax zone. That should be easy enough. Don't do it as a coupon or another problem you're going to run into then is that customers with other coupons won't be able to use them because the "tax free" coupon was automatically applied (zen won't currently allow more than one coupon). Instead, I think you'd probably want to modify the "specials" code to allow a special to only apply for a given zone. Actually, that's not a bad idea for a core upgrade to the code.

Really though, I think you could just charge a zero tax rate and put a notice up that "taxes, where applicable, are included in the price shown." and ignore what OMoR told you. What are they going to do? Nothing. Just make sure you handle the actual accounting side correctly and submit the appropriate tax you "collected" and they'll be happy as clams. I've learned in business, and especially as it relates to government, to just keep it simple and don't ask them questions you don't want to know the answer to.