You can throw from discover_vertex visitor.
Or should I consider this rather a limitation of BGL (rendering it useless for us as I will not introduce exceptions as part of the normal execution path). I wonder if this problem occurs so infrequent that there is no real built-in solution
Like I said before you, can build a visitor that keeps a reference to the BFS's internal queue and flush it when you want to terminate the search. It's not as efficient as throwing an exception since clearing the queue is O(n), but it should still work. You'd probably want to flush the queue on finish_vertex so you guarantee that you won't pick up any new vertices in the next loop.
You could also rewrite the search algorithm to include an explicit stopping point. The core BFS implementation is probably only 20 lines of fairly straightforward code.