SQL Server Management Studio times out connecting to a remote SQL Server engine

Question

I've done this at least a hundred times.

• Install SQL Server on a VPS
• Install it as the default instance
• Only install the engine, not SSMS
• Install Express edition
• Go to SQL Server Configuration Manager
• Enable TCP/IP
• Change port from 1433 to another port
• Open that port in Windows Firewall as Inbound Rule
• Test port using Telnet from another connected machine
• Install SSMS on another machine
• Connect with IP,Port format

And one hundred times it worked. Now I'm stuck. I've done all the steps, and client can't connect to the engine. It simply times out. Here's what I've done:

• Increasing time-out in connection window, but getting this error: A connection was successfully established with the server, but then an error occurred during the pre-login handshake. (provider: TCP Provider, error: 0 - The semaphore timeout period has expired.) (Microsoft SQL Server, Error: 121)
• Connecting to the engine, from within the VPS, using a connection.udl file, and it works just fine
• Making sure that the engine is truly the default instance, using . in connection.udl and it's confirmed
• Enabling ping following this link. Ping was not enabled by default, but for other VPS instances it was working. I compared their firewalls and their rules were just like each other. Yet this one didn't have ping. I enabled ping and still getting time-out
• Installing SSMS on VPS to test any special thing that I'm not aware of, worked. Though SSMS on remote machine is 12.0.5000.0 and on VPS is 12.0.2000.8
• Checking the software that I downloaded. I only downloaded the Express 64BIT\SQLEXPR_x64_ENU.exe from this page, and installed all features of it.

Now I'm totally stuck. I have no idea on what to do next. What other things should I test?