There is no fixed time for them to spawn... This mini world change can happen at anytime... I already found it right after the server save, and i also found it like 10 min before the server save....
My advice for you is to keep watching over the World Board (on the adventurer's guild)
When you see the message "Several banks in major coastal towns are being robbed! The thieves are still on the loose!"
you will know that there is a boss on the loose... (be aware, that this message will dissapear only after delivering the "bag with stolen gold", or (if no one delivery it) on the next server save)
Also, be aware that the "bag with stolen gold" will dissapear 24h after you getting it... so don't try to keep it, its better to delivery for the achievement or to sell it to someone else. (also, you can't delivery it after the server save, since the world change will be gone.)