Miners could still game this by including all "real" high fee txs and then filling the block with tx back to addresses controlled by the miner (with high fees = going right back to miner anyways).
Yes, this will be the most difficult challenge to solve. You could make the lottery-reward decrease exponentially with the number of transactions in the block, making it unprofitable for miners to add extra fake transactions. Since they will have the chance to loose all the high fees for a slim chance on a small reward. In other words: each extra fake transaction will mean they pay more to win less.
Another solution could be that the network rejects blocks of which a certain percentage of the transactions is not in their memory pool. That means the miner has to broadcast those TX's first, and if another miner mines the block, the miner who created the fake TX's looses a lot of money.