Hi;
I solved a similar problem, but it's even in the local subnet. I can connect to tcp/311 and tcp/625 from (remote) to (server) -- of course the connection is dropped as soon as I type anything but is confirmed with netstat and tcpdump -- and the checkbox for remote administration is enabled.
Connection is refused identically whether using the correct password or not: the annoying shake-the-dialog animation, and ZERO detail about the failure. The dialog doesn't even register any red text to help indicate why it's shaking, I simply assume it's an authentication issue.
System Preferences, FWIW, show "Sharing->Remote Management" both "on" and "allow all users". Shared Screen works fine to this host, but the host is slow to respond due to workload, the show cursor movement makes me less frustrated if I could just Server.App it.
I found that my server failued to update the external name (so server109.local is also server109.example.com on the internet, and when I connected to server109.local, it seemed to retry to server109.example.com). server109.example.com (or whatever your public-service IP address) might not be working correctly... so when trying to telnet to tcp/311 or tcp/625, check all addresses that your Server.App shows on the first screen in the "Server" section, above "Alerts".