The problem was: The server certificate was signed with a SHA-512 hash. Debian 7 still comes with gnutls 2.x, but gnutls 3.x is required to savely use SHA-512 signed certificates. I was installing this certificate on Dec 23, 2014.
Google seems to have altered their policies in cipher negotiation to be more strict on fall back cipher suits and/or signature checking. Until end of Jan 2015, mail exchange with gmail servers worked (with the Debian 7 + gnutls 2.6 + SHA-512 signed CRT configuration), then it suddenly dropped, so no emails could be received from gmail after end of January 2015 without changes on my side.
Solution: Substituting for an SHA-256 signed Certificate or upgrading to gnutls 3.x (which is currently not in the stable branch of Debian 7) solves the problem. (I did the first.)
Note 1: Researching online I found out that this is also a problem of many non-commertial CaCert.org certificates which are SHA-512 signed by default now. It seems that CaCert.org now provides an "advanced option" in the CRT generation interface to select SHA-256 to avoid this problem for Debian 7 users. However, on this precise issue there is currently a lot of misleading hints and suggestions in online forums, saying that the tls_require_ciphers variable must be set properly in the exim4 configuation to ensure proper cipher suite negotiation. This is wrong; I did not adjust this variable at all.
Note 2: There is a related problem concerning customers using Thunderbird connecting to an exim4 + Debian 7 MTA for sending mail (see this post: Exim after Thunderbird update: "Could not negotiate a supported cipher suite" , which was closed but is in fact highly related.)
Thunderbird has exactly the same strict configuration as gmail uses when negotiatin cipher suite, so it fails in this particular circumstances when the server uses gnutls < 3.x but an SHA-512 signed CRT. The solution is the same: Use a SHA-256 signed CRT or update libgnutls (if possible in your distribution).
