Sure, there will be small amounts of fraud— there always is— but if cash didn't kill taxes, Bitcoin sure won't. The incentives are just setup to make tax fraud at any real scale unattractive.
Each person must publicly declare the bitcoin addresses that they hold. Any legitimate business accepting payment in bitcoins can only receive bitcoins from other registered addresses, else they are black flagged and no longer a registered address.
Now, your average business and the banks are not going to circumvent these rules. The Banks will probably give their business customers payment gateways that enforce these rules without the business having any choice. Black market bitcoins will still exist, they will just be useless as "normal" currency and will be completely separate, with no way to cross over. Since all transactions are public it is trivial for the government to enforce these rules.
You'll still be able to run your exchange in some other political jurisdiction, but unless the Government white lists your addresses, nobody will be able to spend those coins on legitimate businesses in your country.
This particular implementation wouldn't actually work. Anyone can send BTC to any address, so it would be easy to poison the well.
(But I suspect some similar scheme could be feasible. You might be able to enforce the rule on BTC->$ withdrawls? I wonder about mixers, though.)
You could easily have software that would automatically turn over to the government any coins sent from addresses that are not registered. It's like if you found a briefcase full of money: you'd turn it over to the police (or maybe you wouldn't, but that's what you should do). With software, it could just be automatic.
If you refuse to run software that does this, or you don't turn over coins received from blacklisted sources within some period of time, you get blacklisted.
[1] By design, Bitcoin addresses are supposed to be single-use. Reusing them is a security risk and not recommended (recent android vulnerability is a good example - it only affected reused addresses). Every transaction done with the standard client usually creates a new address (to send the change), which is not even visible in the interface. Merchants accepting Bitcoin usually create a new address for each invoice, etc. etc.
In other words, the way Bitcoin is used is fundamentally incompatible with the public declaration of addresses. If the government has the power to change this, it might as well make Bitcoin completely illegal and not bother.