It was a timing issue. The server was sending <proceed> and then started to build the TLS setup. Clients where sometimes faster than the server and started to request TLS and the server then responded that TLS was not supported. The solution is to build the TLS setup first, then send the <proceed> and finally start the handshake.
Sometimes clients are not able to secure a connection using TLS. This problem also affects s2s.