I have (hopefully) fixed this bug upstream now (commit 0d29084a864c).In case of a shutdown of cups-browsed the queues were even removed with jobs. This I have corrected now, now cups-browsed really only removes print queues when they do not have jobs.
The problem occurred independent of whether the remote queues are discovered from the local network or via BrowsePoll.
Till