Okay so I quite like this idea. If we start removing at height 630000 or 840000 (gives us 4-8 years to develop this solution), it stays nice and neat with the halving interval. We can look at this like so:

B - the current block number
P - how many blocks behind current the coin burning block is. (630000, 840000, or otherwise.)

Every time we mine a new block, we go to block (B-P), and check for stale coins. These coins get burnt up and pooled into block B's miner fees. This keeps the mining rewards up in the long term, people are less likely to stop mining due to too low fees. It also encourages people to keep moving their money around the enconomy instead of just hording and leaving it.