I just wanted to verify that I just did not wait long enough for gdm3 to start. I reinstalled linux-image-4.9.0-6-amd64 and now the issue went away! So it seems to be some sort of race condition, whatsoever. I booted at least five times now without a single problem.