HFT's can already be pulled from the market (regardless of how many orders they place) under current regulations. I think the idea of licensing them individually might look good, but really achieves nothing.
I agree about the minimum resting times. It just makes things harder (and more risk of loss) for those who create liquidity. This includes the "good" (non predatory) HFT that creates liquidity.
There is already a tax imposed as you described - it started Jan 2012 in Australia. It's called the "Market Supervision Cost Recovery" levy. It taxes all messages sent to an exchange - either place/amend/cancel.
See http://www.theage.com.au/business/costrecovery-levy-sure-walks-like-a-financial-transactions-tax-20120103-1pjkd.html
