I think a queue is the only solution. But the queue can be implemented in different ways.
The traditional "first come, first served" queue works but has a big flaw, as pointed out by @Spartan.
But what if we made a queue that accounts for priority? One that doesn't let people spam and one that gives a fair chance to everybody.
Says there's currently 7 ads in the queue, but all of those 7 are from people who already placed ads recently. If player X, who hasn't placed any ads recently wants to do so now, his ad would be 1st in the queue and would be displayed almost immediately, and the other 7 will continue waiting in queue. After that, if player X wants to place another ad, it now goes 8th in the queue - the player who had an ad displayed most recently has the lowest priority.
This gets rid of spam and gives everyone a fair chance.
Of course, the queue is just about how the ads are placed. The way the ads are displayed can also be improved as @Spartan mentioned.
On top of that, I strongly agree with @Lance regarding:
