Perhaps dukes should be given the option of appointing rulers to region lord. The region thus becomes a new duchy. Have a little checkbox that they need to click so that the duke does not accidentally do this.
Or, the ruler waits til a duchy becomes available.
The problem with the waiting solution is that it encourages the use of placeholders, since new cities acquired do not immediately generate an empty duchy seat, but instead get placed into an existing duchy.
