I rechecked this against bzr Emacs and GnuTLS 3.0.17 and it's still
there.  I tried to create a smaller test case and came up with this:

$ gnutls-serv --http &
$ emacs -Q

(progn
  (setq gnutls-log-level 5
        message-log-max t)
  (open-protocol-stream
        "*nnimap*" (current-buffer) "localhost"
        5556
        :type 'ssl
        :return-list t
        :shell-command "ssh %s imapd"
        :capability-command "1 CAPABILITY\r\n"
        :end-of-command "\r\n"
        :success " OK "
        :starttls-function
        (lambda (capabilities)
          (when (gnus-string-match-p "STARTTLS" capabilities)
            "1 STARTTLS\r\n"))))

The open-protocol-stream call is how nnimap-open-connection-1 in
lisp/gnus/nnimap.el creates the IMAP network process.

The loop happens when the GnuTLS handshake fails for some reason, within
a network process.  I use the attached patch to limit the number of
iterations.  I'm not familiar enough with the Emacs process code to
suggest a fix though.

It would be nice if one of you could try against gnutls-serv and confirm
you see this -- I think the problem is general enough that this proves
it and will allow a fix that I can test against my IMAP server.

However, if need-be I can try to arrange a tunnel to the IMAP server I'm
trying to connect to.

As for why this hasn't been seen before, it doesn't affect the GnuTLS
backend standalone (as Ted pointed out) -- it seems to only happen when
an SSL-using process is created and the GnuTLS handshake fails, so it
will be rare that it happens.  Still, an infinite loop is not a nice
failure mode, even if it's rare.

Thomas